Sequence Heap

The nerd's description

sequence-heap.js orders elements in streaming-fashion just like any heap, allowing it to be used as a priority queue. Implemented as sorted linked lists, the performance is comparable, but not as good as a binary heap implemented over an array. (Don't have hard numbers at this time).

This variant of a sequence heap maintains the heap invariant by splitting linked lists when they hold too many elements. How many? Specify this with rankFactor. This means each linked list progressing in rank holds rankFactor times more elements than the previous linked list. See Comparison.

In the sequence heap paper by Brodal (see Further Exploration), his definition of a (non-soft) sequence heap implies successive lists double in size. Here the rankFactor is 2.

The townsfolk's description

She holds her hands like an altar of death.

A small dot of light blooms from page, first marigold, light canary, then white and hot before a black circle of cinder appears underneath. Atop the book, the chain worm glows red and convulses. It clinks and rattles, jerking hither and yon, desperate to escape her flames. Its crying both enrages her and stokes her desire to see it squeal, to witness the entire gamut of its wailing in every degree of suffering measured in Kelvin.

Hotter and higher, the flames whip and crackle wildly. A tree three yards away receives a stray lashing and erupts. She unknowingly smiles at this divine euphony dueted by the hellish wailing one could imagine signified regret. She is fire in meditation.

At last her focus breaks when the chain worm's head rockets off and it's crying no longer. Looking around, she remembers how she got to this empty field. How, for a moment, her vengeance gave her a peace amidst tragedy.

Seeking more, seeking the demon's provenance, she incants: npm author ls sequence-heap.

The spell produces a luminescent writing in the air. The knowledge numbs her, takes away her balance which she finds only after falling into the ground….

Enough talk

Install

npm install sequence-heap

Usage

CommonJS:

const SequenceHeap = require('sequence-heap')

ESM:

import SequenceHeap from 'sequence-heap'

Initialize:

// each linked list will increase in size by 4 times compared to the previous linked list
const rankFactor = 4 // default is 2
let heap = new SequenceHeap((a,b) => a - b, rankFactor)

// Fill heap
let i = 10
while(i > 0) {
  heap.insert(Math.random() * 100)
  i--
}

// Prints elements in ascending order
while(heap.size > 0) {
  console.log(heap.pop())
}

Worst Case Time Complexity Comparison

| | sequence heap | binary heap | |----------- |------------------- |----------- | | find_min | O(1)** or O(logn) | O(1) | | insert | O(log(n))* | O(log(n)) | | delete_min | O(log(n)) | O(log(n)) |

* amortized

** reducing peek to O(1) can be done by keeping track of the min from insertions and deletions Watch my video proving time complexity for these operations.

Further exploration

Wikipedia as of 2024-06-13 still has no article on sequence heaps. Prior articles do not necessarily agree on nomenclature either.

• arvix and the paper by Gerth Stølting Brodal where I first learned about sequence heaps while learning about soft heaps.
• Fast priority queues for cached memory
• Fishspear a priority queue algorithm
• Priority Queues and Dijkstra’s Algorithm

Contributing

I would like a house. Please and thank you. Or help editing my writing.

This project lives primarily at sequence-heap.js where issues are best filed. You may sign in or create an account directly, or use one of several OAuth 2.0 providers.

Running Tests

npm run test
# or
npx mocha ./test/*.js