README
Heap.js"> 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.1
- Adds
Heap.nlargest
as heapq. - Adds
Heap.nsmallest
as heapq. - Sanitizes
top
/bottom
input to force an integer. - Linted with Eslint.
2.0
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 anditerator()
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
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);
// priorityQueue === priorityQueue.iterator()
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
length
of the heaplimit
amount of elements in the heappop()
the top elementpush(...elements)
one or more elements to the heappushpop(element)
faster thanpush
&pop
replace(element)
faster thanpop
&push
top(number?)
most valuable elements from the heapbottom(number?)
least valuable elements from the heap
PriorityQueue
interface:
Implements Java's add(element)
to the heapaddAll([elment, element, ... ])
to the heap, faster than loopadd
clear()
clone()
comparator()
contains(element, fn?)
element()
alias ofpeek()
isEmpty()
iterator()
returnsthis
because it is iterableoffer(element)
alias ofadd(element)
peek()
poll()
alias ofpop()
remove(element?)
removeAll()
alias ofclear()
size()
alias oflength
toArray()
toString()
To do:
containsAll
equals
retainAll
heapq
interface:
Implements static Python's Heap.heapify(array, comparator?)
that converts an array to an array-heapHeap.heappop(heapArray, comparator?)
that takes the peek of the array-heapHeap.heappush(heapArray, item, comparator?)
that appends elements to the array-heapHeap.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 iterableHeap.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 array-heapHeap.heapbottom(n, heapArray, comparator?)
that returns then
least valuable elements of the array-heap
To do:
merge(...iterables, comparator?)
Documentation
https://ignlg.github.io/heap-js/
Contributing
Development of Heap.js happens in the open on GitHub, and I am grateful to the community for contributing bugfixes and improvements.
Dev setup
yarn
Tests
npm run test
Benchmarks
npm run benchmarks
License
Heap.js is BSD licensed.