Heap.js

Efficient Binary heap (priority queue, binary tree) data structure for JavaScript / TypeScript.

Includes JavaScript methods, Python's heapq module methods, and Java's PriorityQueue methods.

Easy to use, known interfaces, tested, and well documented JavaScript binary heap library.

Instances are integer min heap by default.

Is it faster than sorting an array?

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)

Changelog

2.2

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 iteraror will consume the heap, as Python's heapq implementation does.

2.1

Adds Heap.nlargest as heapq.
Adds Heap.nsmallest as heapq.
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. It should not be part of the spec for a priority queue, the output should be the top N elements. It will be partially ordered with the peek at index 0 by definition, that is all.

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 topN algorithms.
(wip) Benchmarks.

1.5

Adds Iterator interface and iterator() method.

Examples

// Basic usage example
import Heap from 'heap-js';

const minHeap = new Heap();
const maxHeap = new Heap(Heap.maxComparator);

minHeap.init([5, 18, 1]);
minHeap.push(2);
console.log(minHeap.peek()); //> 1
console.log(minHeap.pop()); //> 1
console.log(minHeap.peek()); //> 2

// Iterator, that will consume the heap
maxHeap.init([3, 4, 1, 12, 8]);
for (const value of maxHeap) {
  console.log('Next top value is', value);
}

// Priority Queue usage example
const { Heap } = require('heap-js');

const tasks = db.collection.find().toArray();
const customPriorityComparator = (a, b) => a.priority - b.priority;

const priorityQueue = new Heap(customPriorityComparator);
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 taks of priorityQueue.iterator()) {
  // Do something
}

// Iterator, the JavaScript and Python way, that will consume the heap
for (const task of priorityQueue) {
  // Do something
}

// Python-like static methods example
import { Heap } from 'heap-js';
const numbers = [2, 3, 7, 5];

Heap.heapify(numbers);
console.log(numbers); //> [ 2, 3, 5, 7 ]

Heap.heappush(numbers, 1);
console.log(numbers); //> [ 1, 2, 5, 7, 3 ]

Installation

yarn add heap-js # if you use yarn

npm install --save heap-js # if you use npm

Constructor

new Heap([comparator]);

Basic comparators already included:

Heap.minComparator Integer min heap (default)
Heap.maxComparator Integer max heap

Implements JavaScript style methods

for (const value of heap) directly usable as an Iterator, consumes the heap
length of the heap
limit amount of elements in the heap
pop() the top element
push(...elements) one or more elements to the heap
pushpop(element) faster than push & pop
replace(element) faster than pop & push
top(number?) most valuable elements from the heap
bottom(number?) least valuable elements from the heap

Implements Java's `PriorityQueue` interface:

add(element) to the heap
addAll([elment, element, ... ]) to the heap, faster than loop add
clear()
clone()
comparator()
contains(element, fn?)
element() alias of peek()
isEmpty()
iterator() returns the same as toArray() because it is iterable and follows Java's implementation
offer(element) alias of add(element)
peek()
poll() alias of pop()
remove(element?)
removeAll() alias of clear()
size() alias of length
toArray()
toString()

To do:

containsAll
equals
retainAll

Implements static Python's `heapq` interface:

Heap.heapify(array, comparator?) that converts an array to an array-heap
Heap.heappop(heapArray, comparator?) that takes the peek of the array-heap
Heap.heappush(heapArray, item, comparator?) that appends elements to the array-heap
Heap.heappushpop(heapArray, item, comparator?) faster than heappush & heappop
Heap.heapreplace(heapArray, item, comparator?) faster than heappop & heappush
Heap.nlargest(n, iterable, comparator?) that gets the n most valuable elements of an iterable
Heap.nsmallest(n, iterable, comparator?) that gets the n least valuable elements of an iterable

Extras:

Heap.heaptop(n, heapArray, comparator?) that returns the n most valuable elements of the array-heap
Heap.heapbottom(n, heapArray, comparator?) that returns the n least valuable elements of the array-heap

To do: