Heap.js

Heap data structure for JavaScript.

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

Instances are integer min heap by default.

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

// 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);

while (let task = priorityQueue.pop()) {
  // 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 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()
• 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
• iterator()
• 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

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:

• merge(...iterables, comparator?)
• nlargest(n, iterable, comparator?)
• nsmallest(n, iterable, comparator?)

Documentation

Extensive documentation included at ./dist/docs. It'll be published to gh-pages in a next release.

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 # if you use yarn

npm install # if you use npm

Tests

yarn test # if you use yarn

npm test # if you use npm

License

Heap.js is BSD licensed.