Efficient Binary heap (priority queue, binary tree) data structure for JavaScript / TypeScript.
Now with support for async comparators with the new HeapAsync
class!
Includes JavaScript methods, Python's heapq module methods, and Java's PriorityQueue methods.
Easy to use, known interfaces, tested, and welldocumented JavaScript binary heap library.
Instances are integer min heap
by default.
It depends on your usage, but for some scenarios, it is much faster:
heap vs array: push + pop/unshift 50
heap x 72,130 ops/sec ±0.50% (93 runs sampled)
array x 121 ops/sec ±78.09% (5 runs sampled)
heap vs array: push + peek 20
heap x 622,332 ops/sec ±27.93% (63 runs sampled)
array x 207 ops/sec ±78.18% (5 runs sampled)
heap vs array: push + top(1) of 100
heap x 124,835 ops/sec ±40.37% (61 runs sampled)
array x 123 ops/sec ±78.49% (5 runs sampled)
heap vs array: push + top(50) of 100
heap x 59,210 ops/sec ±17.66% (82 runs sampled)
array x 125 ops/sec ±78.79% (5 runs sampled)
 Improves the
limit
property to support negative, Infinity, and NaN values. They will be set as0
and the heap will not be limited.  Adds the
setLimit
method to set the limit of the heap. It returnsNaN
if the limit is negative, or NaN. This method is useful to check if the limit was set as expected.  Improves tests and documentation.
 Adds the
indexOf
method to find the first index of an element in the heap.  Adds the
indexOfEvery
method to find all indexes of an element in the heap.  Changes the
remove
method to use theindexOf
method.  Changes the
contains
method to use theindexOf
method.  Improves documentation.
 Adds the
HeapAsync
class, with async methods and supporting async comparators. It is a dropin replacement for theHeap
class with Promises.
 Fixes
.iterator()
method to follow Java's PriorityQueue implementation:The Iterator provided in method iterator() is not guaranteed to traverse the elements of the priority queue in any particular order.
Notice that using the heap directly as an iterator will consume the heap, as Python's heapq
implementation does.
 Adds
Heap.nlargest
as inheapq
.  Adds
Heap.nsmallest
as inheapq
.  Sanitizes
top
/bottom
input to force an integer.  Linted with Eslint.
The main breaking change is that now top(N)
does NOT sort the output, because sorting should not be part of the spec for a priority queue. The output is the top N elements, and they will be partially ordered with the peek at index 0
by definition.

top(N)
is unordered, only the first element is guaranteed to be the top priority element.  Fixes custom heap issue #31.
 Performance improvements.
 More tests, including those for custom heaps.
 Auxiliary experimental
top(N)
algorithms.  (WIP) Benchmarks.
 Adds the
Iterator
interface anditerator()
method.
A heap where the smallest element is always at the top. It is the default heap.
import { Heap } from 'heapjs';
// Min Heap by default
const minHeap = new Heap();
// Initialize the heap with an array
minHeap.init([5, 18, 1]);
// Push a new value
minHeap.push(2);
console.log(minHeap.peek()); //> 1
console.log(minHeap.pop()); //> 1
console.log(minHeap.peek()); //> 2
A heap where the largest element is always at the top.
import { Heap } from 'heapjs';
// Max Heap
const maxHeap = new Heap(Heap.maxComparator);
// Initialize the heap with an array
maxHeap.init([3, 4, 1, 12, 8]);
// Push a new value
maxHeap.push(2);
console.log(maxHeap.peek()); //> 12
console.log(maxHeap.pop()); //> 12
console.log(maxHeap.peek()); //> 8
A heap where the most important element is always at the top, but the elements are objects with a priority
property.
import { Heap } from 'heapjs';
const customPriorityComparator = (a, b) => a.priority  b.priority;
// Custom Heap
const customHeap = new Heap(customPriorityComparator);
// Initialize the heap with an array
customHeap.init([{ priority: 5 }, { priority: 18 }, { priority: 1 }]);
// Push a new value
customHeap.push({ priority: 2 });
console.log(customHeap.peek()); //> { priority: 1 }
console.log(customHeap.pop()); //> { priority: 1 }
console.log(customHeap.peek()); //> { priority: 2 }
A heap where the most important element is always at the top, the elements are objects with a priority
property, and the comparator function is asynchronous. Implements the same interface as Heap
, but almost all methods return a Promise
.
import { HeapAsync } from 'heapjs';
const customPriorityComparator = (a, b) => Promise.resolve(a.priority  b.priority);
// Custom HeapAsync
const customHeap = new HeapAsync(customPriorityComparator);
// Initialize the heap with an array
await customHeap.init([{ priority: 5 }, { priority: 18 }, { priority: 1 }]);
// Push a new value
await customHeap.push({ priority: 2 });
console.log(customHeap.peek()); //> { priority: 1 }
console.log(await customHeap.pop()); //> { priority: 1 }
console.log(await customHeap.peek()); //> { priority: 2 }
Iterates over the heap consuming it, and guarantees to traverse the elements of the heap in the order of priority. Useful.
const { Heap } = require('heapjs');
// Get all tasks from the database
const tasks = db.collection.find().toArray();
// The most important task has the lowest priority value
const customPriorityComparator = (a, b) => a.priority  b.priority;
// Create the priority queue
const priorityQueue = new Heap(customPriorityComparator);
// Initialize the priority queue with the tasks
priorityQueue.init(tasks);
// Iterator that will consume the heap while traversing it in the order of priority
for (const task of priorityQueue) {
console.log(task);
}
Iterates over the heap without consuming it, but does not guarantee to traverse the elements of the heap in any particular order. Barely useful.
const { Heap } = require('heapjs');
// Get all tasks from the database
const tasks = db.collection.find().toArray();
// The most important task has the lowest priority value
const customPriorityComparator = (a, b) => a.priority  b.priority;
const priorityQueue = new Heap(customPriorityComparator);
// Initialize the priority queue with the tasks
priorityQueue.init(tasks);
// Iterator, the Java way, that will not consume the heap BUT does not guarantee to traverse the elements of the heap in any particular order. Barely useful.
for (const task of priorityQueue.iterator()) {
console.log(task);
}
import { Heap } from 'heapjs';
const numbers = [2, 3, 7, 5];
// Changes the array elements order into a heap inplace
Heap.heapify(numbers);
console.log(numbers); //> [ 2, 3, 5, 7 ]
// Pushes a new value to the heap
Heap.heappush(numbers, 1);
console.log(numbers); //> [ 1, 2, 5, 7, 3 ]
yarn add heapjs # if you use yarn
npm install save heapjs # if you use npm
new Heap([comparator]);
new HeapAsync([asyncComparator]);

Heap.minComparator
: Uses lessthan operator to compare elements. It is the default comparator. 
Heap.maxComparator
: Uses greaterthan operator to compare elements. 
Heap.minComparatorNumber
: Uses subtractiona  b
to compare elements. 
Heap.maxComparatorNumber
: Uses subtractionb  a
to compare elements.

for (const value of heap)
directly usable as an Iterator, consumes the heap. 
length
of the heap. 
limit
the number of elements in the heap. 
pop()
the top element. 
push(...elements)
one or more elements to the heap. 
pushpop(element)
faster thanpush
&pop
. 
replace(element)
faster thanpop
&push
. 
top(number?)
most valuable elements from the heap. 
bottom(number?)
least valuable elements from the heap. 
indexOf(element, fn?)
returns the internal index of the first occurrence of the element in the heap. 
indexOfEvery(element, fn?)
returns an array with the internal indexes of all occurrences of the element in the heap.

add(element)
to the heap. 
addAll([element, element, ... ])
to the heap, faster than loopadd
. clear()
clone()
comparator()
contains(element, fn?)
element()
alias ofpeek()
isEmpty()

iterator()
returns the same astoArray()
because it is iterable and follows Java's implementation. Barely useful. Usefor (const value of heap)
instead. offer(element)
alias ofadd(element)
peek()
poll()
alias ofpop()
remove(element?)
removeAll()
alias ofclear()
size()
alias oflength
toArray()
toString()
To do:
containsAll
equals
retainAll

Heap.heapify(array, comparator?)
that converts an array to an arrayheap. 
Heap.heappop(heapArray, comparator?)
that takes the peek of the arrayheap. 
Heap.heappush(heapArray, item, comparator?)
that appends elements to the arrayheap. 
Heap.heappushpop(heapArray, item, comparator?)
faster thanheappush
&heappop
. 
Heap.heapreplace(heapArray, item, comparator?)
faster thanheappop
&heappush
. 
Heap.nlargest(n, iterable, comparator?)
that gets then
most valuable elements of an iterable. 
Heap.nsmallest(n, iterable, comparator?)
that gets then
least valuable elements of an iterable.
Extras:

Heap.heaptop(n, heapArray, comparator?)
that returns then
most valuable elements of the arrayheap 
Heap.heapbottom(n, heapArray, comparator?)
that returns then
least valuable elements of the arrayheap
To do:
merge(...iterables, comparator?)
https://ignlg.github.io/heapjs/
Development of Heap.js happens in the open on GitHub, and I am grateful to the community for contributing bug fixes and improvements.
yarn
npm run test
npm run benchmarks
Heap.js is BSD licensed.