heap-js

What is heap-js?

heap-js is a JavaScript implementation of a binary heap data structure. It provides efficient methods for priority queue operations, such as inserting elements, finding the minimum or maximum element, and removing elements. This package is useful for algorithms that require priority queues, such as Dijkstra's algorithm for shortest paths, Huffman coding, and more.

What are heap-js's main functionalities?

MinHeap

This feature allows you to create a MinHeap, where the smallest element is always at the root. The code sample demonstrates how to insert elements into the MinHeap, peek at the smallest element, and remove elements in ascending order.

const { MinHeap } = require('heap-js');
const minHeap = new MinHeap();
minHeap.push(3);
minHeap.push(1);
minHeap.push(2);
console.log(minHeap.peek()); // Output: 1
console.log(minHeap.pop()); // Output: 1
console.log(minHeap.pop()); // Output: 2

MaxHeap

This feature allows you to create a MaxHeap, where the largest element is always at the root. The code sample demonstrates how to insert elements into the MaxHeap, peek at the largest element, and remove elements in descending order.

const { MaxHeap } = require('heap-js');
const maxHeap = new MaxHeap();
maxHeap.push(3);
maxHeap.push(1);
maxHeap.push(2);
console.log(maxHeap.peek()); // Output: 3
console.log(maxHeap.pop()); // Output: 3
console.log(maxHeap.pop()); // Output: 2

Custom Comparator

This feature allows you to create a heap with a custom comparator function. The code sample demonstrates how to create a MinHeap for objects with a 'priority' property, and how to insert and remove elements based on their priority.

const { MinHeap } = require('heap-js');
const customHeap = new MinHeap({
  compare: (a, b) => a.priority - b.priority
});
customHeap.push({ value: 'task1', priority: 2 });
customHeap.push({ value: 'task2', priority: 1 });
console.log(customHeap.pop().value); // Output: 'task2'

Other packages similar to heap-js

heap

The 'heap' package provides a binary heap implementation with similar functionalities to heap-js. It supports both MinHeap and MaxHeap operations and allows custom comparator functions. However, heap-js is often preferred for its more modern API and better performance in certain use cases.

js-priority-queue

The 'js-priority-queue' package offers a priority queue implementation using a binary heap. It supports custom comparator functions and provides methods for inserting and removing elements. Compared to heap-js, js-priority-queue is more focused on priority queue operations and may have a simpler API for those specific needs.

priorityqueuejs

The 'priorityqueuejs' package provides a priority queue implementation with a binary heap. It supports custom comparator functions and offers methods for inserting and removing elements. While similar to heap-js, priorityqueuejs is designed to be lightweight and easy to use, making it a good choice for simpler applications.

README

Heap.js

Heap data structure for JavaScript and TypeScript.

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

Instances are integer min heap by default.

Recent changes

v1.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
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 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 this because it is iterable
• 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

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.