Heaps: IndexedHeap

Array-based binary min-heap that stores each element's position on the element itself under a configurable property name — the same intrusive technique node-based lists use for links, applied to a heap. The payoff: O(1) has()/findIndex() and O(log n) remove()/update()/replace() by handle, with no scans — a priority queue with efficient reschedule and cancel.

Legend for tables

• API
  • options - an object with optional properties:
    • less(a, b) - a function prototyped as a < b (the default)
    • compare(a, b) - a function prototyped as a - b. See Array.prototype.sort() for more info. Default: null.
      • If specified, it overrides less.
    • indexName - property name (string or symbol) used to store the heap index on elements. Default: 'heapIndex'.
  • value - the element to be stored in the heap. Must be an object — the heap writes the index property on it.
• Complexity
  • O - complexity of an operation
  • O(1) - constant time
  • O(log n) - logarithmic time
  • O(n) - linear time
  • O(k) - linear time proportional to the argument size

heap/indexed-heap.js

Implementation of IndexedHeap.

import IndexedHeap from 'list-toolkit/heap/indexed-heap.js';

const heap = new IndexedHeap({less: (a, b) => a.deadline < b.deadline});
const task = {deadline: 150, run: () => {}};
heap.push(task);

// reschedule: mutate the priority, then update by handle — O(log n), no scan
task.deadline = 42;
heap.update(task);

// cancel: remove by handle — O(log n), no scan
heap.remove(task);

Class IndexedHeap

Methods:

Member	Return type	Description	O
constructor(options, ...args)	IndexedHeap	Create a new heap merging in heaps/arrays/iterables.	O(k)
array	array	The underlying array (a valid binary heap).	O(1)
length	number	The number of elements.	O(1)
isEmpty	truthy/falsy	Checks if the heap is empty.	O(1)
top	element | undefined	The minimum element.	O(1)
peek()	element | undefined	The minimum element. An alias of top.	O(1)
indexName	string | symbol	Property name storing the heap index on elements.	O(1)
findIndex(value)	number	The element's position, or -1 if not in this heap.	O(1)
has(value)	boolean	Check if the element is in this heap.	O(1)
push(value)	this	Add an element.	O(log n)
pop()	element | undefined	Remove and return the minimum element.	O(log n)
pushPop(value)	element	Push, then pop — optimized single sift.	O(log n)
replaceTop(value)	element | undefined	Replace the minimum, re-heapify.	O(log n)
update(value, isDecreased?)	this	Re-heapify after mutating an element's priority (by handle).	O(log n)
updateTop()	this	Re-heapify after mutating the top element.	O(log n)
siftFrom(index)	this	Restore the heap property at index (direction detected).	O(log n)
remove(value)	this	Remove an element by handle.	O(log n)
removeByIndex(index)	this	Remove the element at an index.	O(log n)
replace(value, newValue)	this	Replace an element by handle, re-heapify.	O(log n)
replaceByIndex(index, value)	this	Replace the element at an index, re-heapify.	O(log n)
merge(...args)	this	Merge heaps/arrays/iterables, rebuild. Heap arguments are drained.	O(n)
build()	this	Heapify array in place, restamp all indices.	O(n)
clear()	this	Clear the heap.	O(1)
releaseSorted()	array	Heap-sort in place (reverse less order), detach and return.	O(n log n)
make(...args)	IndexedHeap	Create a new heap with the same options.	O(k)

Static members:

Member	Return type	Description	O
from(values, options)	IndexedHeap	Create a heap from an iterable (an array is adopted). Floyd.	O(k)
defaults	object	Default {less, equal, compare, indexName} options.	O(1)

Notes on properties and methods

Elements must be objects. The heap writes its position onto each element under indexName and sets it to -1 when the element leaves the heap. The index property is bookkeeping — treat it as owned by the heap.

The same object can live in several heaps at once — give each heap its own indexName (string or symbol), exactly like lists use custom link names. A symbol keeps the bookkeeping invisible to JSON.stringify and enumeration.

update(value, isDecreased?): after mutating an element's priority, call update to restore the heap. Pass isDecreased = true/false when the direction is known (skips one comparison); omit it to auto-detect. This is the classic decrease-key — the operation that turns a heap into a practical timer/priority queue with rescheduling (compare MinHeap's updateByIndex, which needs an O(n) scan to locate the element first).

merge() drains heap arguments — an element tracks exactly one position per index name, so elements move rather than being shared. Arrays/iterables passed to merge are copied as element sources.

There is deliberately no clone(): two heaps cannot both track the same elements under one index name.

releaseSorted() matches MinHeap's semantics: the returned array is sorted in reverse less order; the heap becomes empty and all indices are reset.

Exports

IndexedHeap is the default export and is also exported by name.