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

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)

- 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 iteraror will consume the heap,* as Python's `heapq`

implementation does.

- Adds
`Heap.nlargest`

as heapq. - Adds
`Heap.nsmallest`

as 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*. It should not be part of the spec for a priority queue, the output should be the top N elements. It will be

`0`

by definition, that is all.`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 topN algorithms.
- (wip) Benchmarks.

- Adds
`Iterator`

interface and`iterator()`

method.

`// 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, that will consume the heap

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

// 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 taks of priorityQueue.iterator()) {

// Do something

}

// Iterator, the JavaScript and Python way, that will consume the heap

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 ]

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

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

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

Basic comparators already included:

`Heap.minComparator`

Integer min heap*(default)*`Heap.maxComparator`

Integer max heap

`for (const value of heap)`

directly usable as an Iterator, consumes the heap`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

`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 the same as`toArray()`

because it is iterable and follows Java's implementation`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 bugfixes and improvements.

```
yarn
```

```
npm run test
```

```
npm run benchmarks
```

Heap.js is BSD licensed.

Generated using TypeDoc