nanoheap

Tiny, zero-dependency binary heap (priority queue) for JavaScript and TypeScript.

A binary heap keeps the highest-priority element at the root, making it the natural backing structure for priority queues, schedulers, top-k selection, and graph algorithms like Dijkstra's. nanoheap ships a single generic Heap<T> class with a comparator-based API, dual ESM/CJS builds, and full type definitions — in ~1.5 kB gzipped.

Install

npm install @ossedb/nanoheap

Requires Node 18+ (or any modern bundler/browser).

Usage

import { Heap, maxComparator } from '@ossedb/nanoheap';

// Min-heap over natural ordering (the default)
const heap = new Heap<number>();
heap.push(5, 1, 4);
heap.peek(); // 1
heap.pop();  // 1
heap.pop();  // 4

// Max-heap
const max = new Heap<number>(maxComparator);
max.push(5, 1, 4);
max.pop(); // 5

// O(n) construction from any iterable (the input is never mutated)
const fromArray = Heap.from([9, 3, 7, 1]);

// Custom comparator — e.g. a priority queue of tasks
type Task = { name: string; priority: number };
const queue = new Heap<Task>((a, b) => a.priority - b.priority);
queue.push({ name: 'deploy', priority: 2 }, { name: 'hotfix', priority: 1 });
queue.pop(); // { name: 'hotfix', priority: 1 }

// Iteration yields priority order without consuming the heap
[...fromArray]; // [1, 3, 7, 9]

API

The comparator has the standard Array.prototype.sort signature: (a, b) => number, negative when a has higher priority. The element with the lowest comparator value is at the root.

| Member | Description | Complexity | | --- | --- | --- | | new Heap<T>(compare?) | Empty heap; defaults to a min-heap over </> | O(1) | | Heap.from(items, compare?) | Heap from any iterable (bottom-up heapify, input copied) | O(n) | | size | Number of elements | O(1) | | isEmpty() | Whether the heap is empty | O(1) | | peek() | Highest-priority element, or undefined | O(1) | | push(...items) | Insert elements; returns this for chaining | O(log n) each | | pop() | Remove and return the root, or undefined | O(log n) | | replace(item) | pop() + push(item) with a single sift | O(log n) | | pushPop(item) | push(item) + pop(); skips sifting when possible | O(log n) | | clone() | Independent shallow copy (shares the comparator) | O(n) | | toArray() | Copy of the backing array in heap order (not sorted) | O(n) | | clear() | Remove all elements | O(1) | | [Symbol.iterator]() | Yields elements in priority order without consuming the heap | O(n log n) total |

Notes

• replace and pushPop are the classic single-sift optimisations (as in Python's heapq.heapreplace/heappushpop) — use them for fixed-size top-k windows.
• Sifting moves a "hole" through the tree with one final write instead of pairwise swaps, and construction uses bottom-up heapify, so hot paths stay allocation-free.
• toArray() returns heap order. For sorted output, spread the heap: [...heap].

License

MIT © Ossama Edbali