## 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.

## Heap.js

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

**Now with support for async comparators with the new **`HeapAsync`

class!

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)
```

### Star History

### Changelog

#### 2.5

- Improves the
`limit`

property to support negative, Infinity, and NaN values. They will be set as `0`

and the heap will not be limited. - Adds the
`setLimit`

method to set the limit of the heap. It returns `NaN`

if the limit is negative, or NaN. This method is useful to check if the limit was set as expected. - Improves tests and documentation.

#### 2.4

- Adds the
`indexOf`

method to find the first index of an element in the heap. - Adds the
`indexOfEvery`

method to find all indexes of an element in the heap. - Changes the
`remove`

method to use the `indexOf`

method. - Changes the
`contains`

method to use the `indexOf`

method. - Improves documentation.

#### 2.3

- Adds the
`HeapAsync`

class, with async methods and supporting async comparators. It is a drop-in replacement for the `Heap`

class with Promises.

#### 2.2

Notice that *using the heap directly as an iterator will consume the heap,* as Python's `heapq`

implementation does.

#### 2.1

- Adds
`Heap.nlargest`

as in `heapq`

. - Adds
`Heap.nsmallest`

as in `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, because sorting should not be part of the spec for a priority queue. The output is the top N elements, and they will be *partially ordered* with the peek at index `0`

by definition.

`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
`top(N)`

algorithms. - (WIP) Benchmarks.

#### 1.5

- Adds the
`Iterator`

interface and `iterator()`

method.

### Examples

#### Basic usage

##### Min Heap

A heap where the smallest element is always at the top. It is the default heap.

```
import { Heap } from 'heap-js';
const minHeap = new Heap();
minHeap.init([5, 18, 1]);
minHeap.push(2);
console.log(minHeap.peek());
console.log(minHeap.pop());
console.log(minHeap.peek());
```

##### Max Heap

A heap where the largest element is always at the top.

```
import { Heap } from 'heap-js';
const maxHeap = new Heap(Heap.maxComparator);
maxHeap.init([3, 4, 1, 12, 8]);
maxHeap.push(2);
console.log(maxHeap.peek());
console.log(maxHeap.pop());
console.log(maxHeap.peek());
```

##### Custom Heap

A heap where the most important element is always at the top, but the elements are objects with a `priority`

property.

```
import { Heap } from 'heap-js';
const customPriorityComparator = (a, b) => a.priority - b.priority;
const customHeap = new Heap(customPriorityComparator);
customHeap.init([{ priority: 5 }, { priority: 18 }, { priority: 1 }]);
customHeap.push({ priority: 2 });
console.log(customHeap.peek());
console.log(customHeap.pop());
console.log(customHeap.peek());
```

##### Min HeapAsync

A heap where the most important element is always at the top, the elements are objects with a `priority`

property, and the comparator function is asynchronous. Implements the same interface as `Heap`

, but almost all methods return a `Promise`

.

```
import { HeapAsync } from 'heap-js';
const customPriorityComparator = (a, b) => Promise.resolve(a.priority - b.priority);
const customHeap = new HeapAsync(customPriorityComparator);
await customHeap.init([{ priority: 5 }, { priority: 18 }, { priority: 1 }]);
await customHeap.push({ priority: 2 });
console.log(customHeap.peek());
console.log(await customHeap.pop());
console.log(await customHeap.peek());
```

#### Priority Queue usage

##### JavaScript / Python-style iterator (recommended)

Iterates over the heap consuming it, and guarantees to traverse the elements of the heap in the order of priority. Useful.

```
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);
for (const task of priorityQueue) {
console.log(task);
}
```

##### Java-style iterator (not recommended)

Iterates over the heap without consuming it, but does not guarantee to traverse the elements of the heap in any particular order. Barely useful.

```
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);
for (const task of priorityQueue.iterator()) {
console.log(task);
}
```

#### Python-like static methods

```
import { Heap } from 'heap-js';
const numbers = [2, 3, 7, 5];
Heap.heapify(numbers);
console.log(numbers);
Heap.heappush(numbers, 1);
console.log(numbers);
```

### Installation

```
yarn add heap-js
npm install --save heap-js
```

### Constructor

#### Heap

```
new Heap([comparator]);
```

#### HeapAsync

```
new HeapAsync([asyncComparator]);
```

### Comparators already included

`Heap.minComparator`

: Uses less-than operator to compare elements. It is the default comparator.`Heap.maxComparator`

: Uses greater-than operator to compare elements.`Heap.minComparatorNumber`

: Uses subtraction `a - b`

to compare elements.`Heap.maxComparatorNumber`

: Uses subtraction `b - a`

to compare elements.

### Implements JavaScript-style methods

`for (const value of heap)`

directly usable as an Iterator, **consumes the heap.**`length`

of the heap.`limit`

the number 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.`indexOf(element, fn?)`

returns the internal index of the first occurrence of the element in the heap.`indexOfEvery(element, fn?)`

returns an array with the internal indexes of all occurrences of the element in the heap.

### Implements Java's `PriorityQueue`

interface

`add(element)`

to the heap.`addAll([element, 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. Barely useful. Use `for (const value of heap)`

instead.`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:

`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 bug fixes and improvements.

#### Dev setup

```
yarn
```

#### Tests

```
npm run test
```

#### Benchmarks

```
npm run benchmarks
```

#### License

Heap.js is BSD licensed.