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

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)

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

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

- Adds the
`HeapAsync`

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

class with Promises.

- Fixes
`.iterator()`

method to follow Java's PriorityQueue implementation:The Iterator provided in method iterator() is not guaranteed to traverse the elements of the priority queue in any particular order.

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

implementation does.

- Adds
`Heap.nlargest`

as in`heapq`

. - Adds
`Heap.nsmallest`

as in`heapq`

. - Sanitizes
`top`

/`bottom`

input to force an integer. - Linted with Eslint.

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

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

- Adds the
`Iterator`

interface and`iterator()`

method.

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

`import { Heap } from 'heap-js';`

// Min Heap by default

const minHeap = new Heap();

// Initialize the heap with an array

minHeap.init([5, 18, 1]);

// Push a new value

minHeap.push(2);

console.log(minHeap.peek()); //> 1

console.log(minHeap.pop()); //> 1

console.log(minHeap.peek()); //> 2

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

`import { Heap } from 'heap-js';`

// Max Heap

const maxHeap = new Heap(Heap.maxComparator);

// Initialize the heap with an array

maxHeap.init([3, 4, 1, 12, 8]);

// Push a new value

maxHeap.push(2);

console.log(maxHeap.peek()); //> 12

console.log(maxHeap.pop()); //> 12

console.log(maxHeap.peek()); //> 8

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;

// Custom Heap

const customHeap = new Heap(customPriorityComparator);

// Initialize the heap with an array

customHeap.init([{ priority: 5 }, { priority: 18 }, { priority: 1 }]);

// Push a new value

customHeap.push({ priority: 2 });

console.log(customHeap.peek()); //> { priority: 1 }

console.log(customHeap.pop()); //> { priority: 1 }

console.log(customHeap.peek()); //> { priority: 2 }

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

// Custom HeapAsync

const customHeap = new HeapAsync(customPriorityComparator);

// Initialize the heap with an array

await customHeap.init([{ priority: 5 }, { priority: 18 }, { priority: 1 }]);

// Push a new value

await customHeap.push({ priority: 2 });

console.log(customHeap.peek()); //> { priority: 1 }

console.log(await customHeap.pop()); //> { priority: 1 }

console.log(await customHeap.peek()); //> { priority: 2 }

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

// Get all tasks from the database

const tasks = db.collection.find().toArray();

// The most important task has the lowest priority value

const customPriorityComparator = (a, b) => a.priority - b.priority;

// Create the priority queue

const priorityQueue = new Heap(customPriorityComparator);

// Initialize the priority queue with the tasks

priorityQueue.init(tasks);

// Iterator that will consume the heap while traversing it in the order of priority

for (const task of priorityQueue) {

console.log(task);

}

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

// Get all tasks from the database

const tasks = db.collection.find().toArray();

// The most important task has the lowest priority value

const customPriorityComparator = (a, b) => a.priority - b.priority;

const priorityQueue = new Heap(customPriorityComparator);

// Initialize the priority queue with the tasks

priorityQueue.init(tasks);

// Iterator, the Java way, that will not consume the heap BUT does not guarantee to traverse the elements of the heap in any particular order. Barely useful.

for (const task of priorityQueue.iterator()) {

console.log(task);

}

`import { Heap } from 'heap-js';`

const numbers = [2, 3, 7, 5];

// Changes the array elements order into a heap in-place

Heap.heapify(numbers);

console.log(numbers); //> [ 2, 3, 5, 7 ]

// Pushes a new value to the heap

Heap.heappush(numbers, 1);

console.log(numbers); //> [ 1, 2, 5, 7, 3 ]

`yarn add heap-js # if you use yarn`

npm install --save heap-js # if you use npm

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

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

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

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

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

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

https://ignlg.github.io/heap-js/

Development of **Heap.js** happens in the open on GitHub, and I am grateful to the community for contributing bug fixes and improvements.

```
yarn
```

```
npm run test
```

```
npm run benchmarks
```

Heap.js is BSD licensed.

Generated using TypeDoc