Heap data structure for JavaScript projects
Switch branches/tags
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
assets
dist
src
.editorconfig
.gitignore
.travis.yml
LICENSE
README.md
package.json
rollup.config.js
tsconfig.build.json
tsconfig.json
tslint.json
yarn.lock

README.md

Heap.js Heap.js

Build Status Dependencies devDependency Status Coverage Status npm version

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.