@graphty/algorithms / index / IndexedMinHeap
Class: IndexedMinHeap ​
Defined in: indexed/structures/min-heap.ts:10
A binary min-heap over node indices with O(log n) decrease-key, keyed by Float64Array values (graph-format design 14.2, graph-format-design.md:3771). pushOrDecrease is the only operation Dijkstra's inner loop needs: it inserts an absent node and decreases a present one, so the heap never holds a stale duplicate and pop() needs no "is this entry current" check.
Constructors ​
Constructor ​
new IndexedMinHeap(
capacity,tieBreakByIndex?):IndexedMinHeap
Defined in: indexed/structures/min-heap.ts:24
Create an empty heap over node indices in [0, capacity).
Parameters ​
capacity ​
number
The number of distinct node indices the heap may hold
tieBreakByIndex? ​
boolean = false
When true, of two equal keys the lower node index pops first, so the pop order is fully determined by the keys; when false (the default) equal keys pop in an order that depends on the push history
Returns ​
IndexedMinHeap
Methods ​
has() ​
has(
node):boolean
Defined in: indexed/structures/min-heap.ts:44
Whether a node is currently in the heap.
Parameters ​
node ​
number
The node index
Returns ​
boolean
True when the node was pushed and has not been popped since
isEmpty() ​
isEmpty():
boolean
Defined in: indexed/structures/min-heap.ts:35
Whether the heap holds no entries.
Returns ​
boolean
True when the heap holds no entries
keyOf() ​
keyOf(
node):number
Defined in: indexed/structures/min-heap.ts:53
The key a node was last given. Meaningful only while has(node) is true.
Parameters ​
node ​
number
The node index
Returns ​
number
Its key
peekKey() ​
peekKey():
number
Defined in: indexed/structures/min-heap.ts:61
The smallest key in the heap, without removing it.
Returns ​
number
The minimum key, or Infinity when the heap is empty
pop() ​
pop():
number
Defined in: indexed/structures/min-heap.ts:104
Remove and return the node with the smallest key. Undefined behaviour on an empty heap; callers guard with isEmpty().
Returns ​
number
The node index
push() ​
push(
node,key):void
Defined in: indexed/structures/min-heap.ts:71
Insert a node that is not in the heap.
Parameters ​
node ​
number
The node index
key ​
number
Its key
Returns ​
void
Throws ​
RangeError when the node index is outside [0, capacity)
pushOrDecrease() ​
pushOrDecrease(
node,key):void
Defined in: indexed/structures/min-heap.ts:87
Insert the node, or lower its key if it is already present and the new key is smaller.
Parameters ​
node ​
number
The node index
key ​
number
Its candidate key
Returns ​
void