IndexedHeap

Example: Usage

import { IndexedHeap } from "@ende/data-structures/unstable-indexed-heap";
import { assertEquals } from "@ende/assert";

const heap = new IndexedHeap<string>();
heap.push("a", 3);
heap.push("b", 1);
heap.push("c", 2);

assertEquals(heap.peek(), { key: "b", priority: 1 });
assertEquals(heap.pop(), { key: "b", priority: 1 });
assertEquals(heap.size, 2);

assertEquals([...heap.drain()], [
  { key: "c", priority: 2 },
  { key: "a", priority: 3 },
]);

Example: Max-heap via descend

import { IndexedHeap } from "@ende/data-structures/unstable-indexed-heap";
import { descend } from "@ende/data-structures";
import { assertEquals } from "@ende/assert";

const heap = new IndexedHeap<string>(null, { compare: descend });
heap.push("a", 1);
heap.push("b", 5);
heap.push("c", 3);

assertEquals(heap.peek(), { key: "b", priority: 5 });

Example: Tuple priority for stable tie-breaking

import { IndexedHeap } from "@ende/data-structures/unstable-indexed-heap";
import { assertEquals } from "@ende/assert";

// Order primarily by score, then by insertion order for ties.
const heap = new IndexedHeap<string, [number, number]>(null, {
  compare: (a, b) => a[0] - b[0] || a[1] - b[1],
});
heap.push("first", [5, 0]);
heap.push("second", [5, 1]);
heap.push("third", [3, 2]);

assertEquals([...heap.drain()].map((e) => e.key), [
  "third",
  "first",
  "second",
]);

constructor

new IndexedHeap(entries?: Iterable<readonly [K, P]> | null, ...options: IndexedHeapCompareArgs<P>)

experimental

Creates an empty IndexedHeap, optionally populated from an iterable of [key, priority] pairs and/or configured with a custom comparator. Heapified in linear time.

Use IndexedHeap.from for inputs that are array-like instead of iterable, or to copy from another IndexedHeap.

entries?: Iterable<readonly [K, P]> | null

An optional iterable of [key, priority] pairs. Each key must be unique; duplicates throw a TypeError. Pass null or undefined to create an empty heap with options.

...options: IndexedHeapCompareArgs<P>

Optional configuration when P is number, bigint, or string; required when P is any other type (e.g. tuples or objects) so the heap has a valid comparator. compare overrides the default ascending-numeric ordering; pass descend for max-heap order, or a custom function for tuple/bigint/etc. priorities.

import { IndexedHeap } from "@ende/data-structures/unstable-indexed-heap";
import { assertEquals } from "@ende/assert";

const heap = new IndexedHeap<string>();
assertEquals(heap.size, 0);

import { IndexedHeap } from "@ende/data-structures/unstable-indexed-heap";
import { assertEquals } from "@ende/assert";

const heap = new IndexedHeap<string>([["a", 3], ["b", 1], ["c", 2]]);
assertEquals(heap.peek(), { key: "b", priority: 1 });

import { IndexedHeap } from "@ende/data-structures/unstable-indexed-heap";
import { assertEquals } from "@ende/assert";

const tasks = new Map([["task-a", 3], ["task-b", 1]]);
const heap = new IndexedHeap(tasks);
assertEquals(heap.peek(), { key: "task-b", priority: 1 });

import { IndexedHeap } from "@ende/data-structures/unstable-indexed-heap";
import { descend } from "@ende/data-structures";
import { assertEquals } from "@ende/assert";

const heap = new IndexedHeap<string>([["a", 1], ["b", 5], ["c", 3]], {
  compare: descend,
});
assertEquals(heap.peek(), { key: "b", priority: 5 });

new IndexedHeap(entries?: Iterable<readonly [K, P]> | null, options?: { compare?: (a: P, b: P) => number })

from

static from<K, P = number>(collection: IndexedHeap<K, P>, options?: { compare?: (a: P, b: P) => number }): IndexedHeap<K, P>

experimental

Create a shallow copy of an existing IndexedHeap. The source's comparator is inherited unless options.compare overrides it; when overridden, the copy is re-heapified in O(n).

Because the source already carries a valid comparator, compare stays optional regardless of the priority type P.

collection: IndexedHeap<K, P>

The source IndexedHeap to copy.

options?: { compare?: (a: P, b: P) => number }

Optional configuration. Omitting it inherits the source's comparator; passing compare overrides it and triggers a re-heapify.

Returns

A new heap containing all entries from the source heap.

import { IndexedHeap } from "@ende/data-structures/unstable-indexed-heap";
import { assertEquals } from "@ende/assert";

const original = new IndexedHeap<string>();
original.push("x", 10);
original.push("y", 5);

const copy = IndexedHeap.from(original);
assertEquals(copy.peek(), { key: "y", priority: 5 });
assertEquals(copy.size, 2);
assertEquals(original.size, 2);

import { IndexedHeap } from "@ende/data-structures/unstable-indexed-heap";
import { descend } from "@ende/data-structures";
import { assertEquals } from "@ende/assert";

const minHeap = new IndexedHeap<string>([["a", 1], ["b", 5], ["c", 3]]);
const maxHeap = IndexedHeap.from(minHeap, { compare: descend });

assertEquals(minHeap.peek(), { key: "a", priority: 1 });
assertEquals(maxHeap.peek(), { key: "b", priority: 5 });

static from<K, P = number>(collection: Iterable<readonly [K, P]> | ArrayLike<readonly [K, P]>, ...options: IndexedHeapCompareArgs<P>): IndexedHeap<K, P>

experimental

Create a new IndexedHeap from an iterable or array-like of [key, priority] pairs.

When the priority type P is number, bigint, or string, the default ascend comparator orders correctly and the options bag is optional. For any other P (tuples, objects), the compare option is required at the type level so the heap has a valid comparator — otherwise ascend would silently produce incorrect ordering.

Use the IndexedHeap.from overload that takes an existing IndexedHeap to copy from another heap instead.

collection: Iterable<readonly [K, P]> | ArrayLike<readonly [K, P]>

An iterable or array-like of [key, priority] pairs.

...options: IndexedHeapCompareArgs<P>

Optional configuration when P is number, bigint, or string; required when P is any other type. compare overrides the default ascending-numeric ordering.

Returns

A new heap containing all entries from the collection.

import { IndexedHeap } from "@ende/data-structures/unstable-indexed-heap";
import { assertEquals } from "@ende/assert";

const heap = IndexedHeap.from([["a", 3], ["b", 1], ["c", 2]]);
assertEquals(heap.peek(), { key: "b", priority: 1 });
assertEquals(heap.size, 3);

import { IndexedHeap } from "@ende/data-structures/unstable-indexed-heap";
import { assertEquals } from "@ende/assert";

const map = new Map([["task-a", 3], ["task-b", 1]]);
const heap = IndexedHeap.from(map);
assertEquals(heap.peek(), { key: "task-b", priority: 1 });

import { IndexedHeap } from "@ende/data-structures/unstable-indexed-heap";
import { assertEquals } from "@ende/assert";

const heap = IndexedHeap.from<string, [number, number]>(
  [["a", [5, 0]], ["b", [3, 1]]],
  { compare: (a, b) => a[0] - b[0] || a[1] - b[1] },
);
assertEquals(heap.peek(), { key: "b", priority: [3, 1] });

static from<K, P = number>(collection: IndexedHeap<K, P> | Iterable<readonly [K, P]> | ArrayLike<readonly [K, P]>, options?: { compare?: (a: P, b: P) => number }): IndexedHeap<K, P>

[Symbol.toStringTag]

readonly [Symbol.toStringTag]: "IndexedHeap"

experimental

A string tag for the class, used by Object.prototype.toString().

import { IndexedHeap } from "@ende/data-structures/unstable-indexed-heap";
import { assertEquals } from "@ende/assert";

const heap = new IndexedHeap<string>();
assertEquals(heap[Symbol.toStringTag], "IndexedHeap");

push

push(key: K, priority: P): void

experimental

Insert a new key with the given priority. Throws if the key already exists — use set for upsert semantics instead.

key: K

The key to insert.

priority: P

The priority (smaller = higher priority by default).

import { IndexedHeap } from "@ende/data-structures/unstable-indexed-heap";
import { assertEquals } from "@ende/assert";

const heap = new IndexedHeap<string>();
heap.push("task-1", 10);
assertEquals(heap.size, 1);
assertEquals(heap.peek(), { key: "task-1", priority: 10 });

pop

pop(): HeapEntry<K, P> | undefined

experimental

Remove and return the front entry (smallest priority), or undefined if the heap is empty. The returned entry is removed from the heap so the caller owns it.

Returns

The front entry, or undefined if empty.

import { IndexedHeap } from "@ende/data-structures/unstable-indexed-heap";
import { assertEquals } from "@ende/assert";

const heap = new IndexedHeap<string>();
heap.push("a", 2);
heap.push("b", 1);

assertEquals(heap.pop(), { key: "b", priority: 1 });
assertEquals(heap.pop(), { key: "a", priority: 2 });
assertEquals(heap.pop(), undefined);

peek

peek(): HeapEntry<K, P> | undefined

experimental

Return the front entry (smallest priority) without removing it, or undefined if the heap is empty.

The returned entry is a fresh wrapper, but for object-typed priorities the priority field shares its reference with the heap — see the class-level note on treating object priorities as immutable.

Returns

A wrapper around the front entry, or undefined if empty.

import { IndexedHeap } from "@ende/data-structures/unstable-indexed-heap";
import { assertEquals } from "@ende/assert";

const heap = new IndexedHeap<string>();
heap.push("x", 5);
heap.push("y", 3);

assertEquals(heap.peek(), { key: "y", priority: 3 });
assertEquals(heap.size, 2);

peekKey

peekKey(): K | undefined

experimental

Return the key of the front entry (smallest priority), or undefined if the heap is empty. Unlike peek, does not allocate a wrapper object.

Returns

The key of the front entry, or undefined if empty.

import { IndexedHeap } from "@ende/data-structures/unstable-indexed-heap";
import { assertEquals } from "@ende/assert";

const heap = new IndexedHeap<string>();
heap.push("x", 5);
heap.push("y", 3);

assertEquals(heap.peekKey(), "y");
assertEquals(heap.size, 2);

peekPriority

peekPriority(): P | undefined

experimental

Return the priority of the front entry (smallest priority), or undefined if the heap is empty. Unlike peek, does not allocate a wrapper object.

Returns

The priority of the front entry, or undefined if empty.

import { IndexedHeap } from "@ende/data-structures/unstable-indexed-heap";
import { assertEquals } from "@ende/assert";

const heap = new IndexedHeap<string>();
heap.push("x", 5);
heap.push("y", 3);

assertEquals(heap.peekPriority(), 3);
assertEquals(heap.size, 2);

delete

delete(key: K): boolean

experimental

Remove the entry with the given key.

key: K

The key to remove.

Returns

true if the key was present, false otherwise.

import { IndexedHeap } from "@ende/data-structures/unstable-indexed-heap";
import { assertEquals } from "@ende/assert";

const heap = new IndexedHeap<string>();
heap.push("a", 1);
heap.push("b", 2);

assertEquals(heap.delete("a"), true);
assertEquals(heap.delete("z"), false);
assertEquals(heap.size, 1);

set

set(key: K, priority: P): void

experimental

Set the priority of a key, inserting it if absent. This is the upsert counterpart to push (which throws on existing keys) and is the natural operation for relaxation steps in graph algorithms like Dijkstra's.

When key already exists, the no-op fast path uses reference equality (===) to skip work when the new priority is identical to the old. For object/tuple priorities this means a structurally-equal but distinct reference still replaces the stored reference and runs a sift (no observable reorder, but not free). See the class-level note on treating object priorities as immutable.

key: K

The key to insert or update.

priority: P

The priority to set.

import { IndexedHeap } from "@ende/data-structures/unstable-indexed-heap";
import { assertEquals } from "@ende/assert";

const heap = new IndexedHeap<string>();
heap.set("a", 10);
assertEquals(heap.getPriority("a"), 10);

heap.set("a", 5);
assertEquals(heap.getPriority("a"), 5);

import { IndexedHeap } from "@ende/data-structures/unstable-indexed-heap";
import { assertEquals } from "@ende/assert";

const heap = new IndexedHeap<string>();
heap.push("a", 10);
heap.push("b", 20);

heap.set("b", 1);
assertEquals(heap.peek(), { key: "b", priority: 1 });

has

has(key: K): boolean

experimental

Check whether the key is in the heap.

key: K

The key to look up.

Returns

true if the key is present, false otherwise.

import { IndexedHeap } from "@ende/data-structures/unstable-indexed-heap";
import { assertEquals } from "@ende/assert";

const heap = new IndexedHeap<string>();
heap.push("a", 1);

assertEquals(heap.has("a"), true);
assertEquals(heap.has("b"), false);

getPriority

getPriority(key: K): P | undefined

experimental

Return the priority of the given key, or undefined if not present.

key: K

The key to look up.

Returns

The priority of the key, or undefined if not present.

import { IndexedHeap } from "@ende/data-structures/unstable-indexed-heap";
import { assertEquals } from "@ende/assert";

const heap = new IndexedHeap<string>();
heap.push("a", 42);

assertEquals(heap.getPriority("a"), 42);
assertEquals(heap.getPriority("b"), undefined);

size

get size(): number

experimental

The number of entries in the heap.

Returns

The number of entries in the heap.

import { IndexedHeap } from "@ende/data-structures/unstable-indexed-heap";
import { assertEquals } from "@ende/assert";

const heap = new IndexedHeap<string>();
assertEquals(heap.size, 0);
heap.push("a", 1);
assertEquals(heap.size, 1);

clear

clear(): void

experimental

Remove all entries from the heap.

import { IndexedHeap } from "@ende/data-structures/unstable-indexed-heap";
import { assertEquals } from "@ende/assert";

const heap = new IndexedHeap<string>();
heap.push("a", 1);
heap.push("b", 2);
heap.clear();

assertEquals(heap.size, 0);
assertEquals(heap.isEmpty(), true);

isEmpty

isEmpty(): boolean

experimental

Check whether the heap is empty.

Returns

true if the heap is empty, false otherwise.

import { IndexedHeap } from "@ende/data-structures/unstable-indexed-heap";
import { assertEquals } from "@ende/assert";

const heap = new IndexedHeap<string>();
assertEquals(heap.isEmpty(), true);

heap.push("a", 1);
assertEquals(heap.isEmpty(), false);

drain

drain(): IterableIterator<HeapEntry<K, P>>

experimental

Create an iterator that removes and yields every entry from smallest to largest priority. The heap is empty when the iterator finishes. If iteration is abandoned early (e.g. via break), the heap retains the remaining entries.

Returns

An iterator yielding entries from smallest to largest priority.

import { IndexedHeap } from "@ende/data-structures/unstable-indexed-heap";
import { assertEquals } from "@ende/assert";

const heap = new IndexedHeap<string>();
heap.push("a", 3);
heap.push("b", 1);
heap.push("c", 2);

assertEquals([...heap.drain()], [
  { key: "b", priority: 1 },
  { key: "c", priority: 2 },
  { key: "a", priority: 3 },
]);
assertEquals(heap.size, 0);

toArray

toArray(): HeapEntry<K, P>[]

experimental

Return a shallow copy of all entries as an array. The order is the internal heap-array order (not sorted by priority). The heap is not modified.

Use drain to retrieve entries in sorted (smallest-first) order.

Each returned entry is a fresh wrapper, but for object-typed priorities the priority field shares its reference with the heap — see the class-level note on treating object priorities as immutable.

Returns

An array of entries in arbitrary (heap-internal) order.

import { IndexedHeap } from "@ende/data-structures/unstable-indexed-heap";
import { assertEquals } from "@ende/assert";

const heap = new IndexedHeap<string>();
heap.push("a", 3);
heap.push("b", 1);
heap.push("c", 2);

const arr = heap.toArray();
assertEquals(arr.length, 3);
assertEquals(heap.size, 3);

[Symbol.iterator]

[Symbol.iterator](): IterableIterator<HeapEntry<K, P>>

experimental

Yield all entries without removing them. The order is the internal heap-array order (not sorted by priority). The heap is not modified (unlike BinaryHeap, whose iterator drains).

Use drain to iterate in sorted (smallest-first) order (which empties the heap).

Mutating the heap (push, pop, set, delete, clear) while iterating is not supported and may skip or repeat entries.

Each yielded entry is a fresh wrapper, but for object-typed priorities the priority field shares its reference with the heap — see the class-level note on treating object priorities as immutable.

Returns

An iterator yielding entries in arbitrary (heap-internal) order.

import { IndexedHeap } from "@ende/data-structures/unstable-indexed-heap";
import { assertEquals } from "@ende/assert";

const heap = new IndexedHeap<string>();
heap.push("a", 3);
heap.push("b", 1);
heap.push("c", 2);

const keys = [...heap].map((e) => e.key);
assertEquals(keys.length, 3);
assertEquals(heap.size, 3);