build push pop push+pop TinyQueue 110ms 110ms 624ms 205ms FlatQueue 85ms 85ms 157ms 112ms Heapify 32ms 41ms 150ms 112ms
Host machine: 2.4 GHz Dual-Core Intel Core i7, 16 GB RAM.
Note: the build operation doesn't actually exist in TinyQueue and FlatQueue, so it has to be replaced with a manual push operation. That's why build times for those two cases are the same as for push.
- push: O(log n)
- pop: O(log n)
- peek: O(1)
- creation with pre-existing list of priorities: O(n)
- runs on browser and Node.js with support to ES6 modules
- tiny code base (under 100 LoC)
- no dependencies
- supports several types of priorities and keys
- standalone heap structures
- max heaps
- unique items
- accessing arbitrary items
- changing the priority of arbitrary items
- objects as keys (with performance hit)
- dynamic size
How to install
npm i heapify
Or if you're a yarn person:
yarn add heapify
If you're on a browser, there's also the option of using a CDN:
import Heapify from "https://unpkg.com/heapify";
And to import a specific version:
import Heapify from "https://email@example.com";
How to use
import Heapify from "heapify"; const queue = new Heapify(); queue.push(1, 10); queue.push(2, 5); queue.pop(); // 2 queue.peek(); // 1 queue.clear(); queue.pop(); // undefined
npm run test
For benchmark tests:
npm run bench
new Heapify(capacity = 64, keys = , priorities = , KeysBackingArrayType = Uint32Array, PrioritiesBackingArrayType = Uint32Array)
Creates a new priority queue. Parameters are:
capacity: the size of the underlying typed arrays backing the heap;
keys: an optional array of pre-existing keys. Provide
to skip this field;
priorities: an optional array of pre-existing priorities. Must match number of keys above. Provide
to skip this field;
KeysBackingArrayType: the array type to be used for keys;
PrioritiesBackingArrayType: the array type to be used for priorities.
const queue1 = new Heapify(32); const queue2 = new Heapify(16, , , Uint64Array, Uint32Array);
Effectively empties the queue. The heap capacity is not changed, nor its elements get erased in any way; it's just the variable that tracks the length that gets cleared to zero, so it's a very cheap operation.
const queue = new Heapify(); queue.push(1, 10); console.info(queue.length); // 1 queue.clear(); console.info(queue.length); // 0
Gets the key with the smallest priority, but does not remove it from the queue.
const queue = new Heapify(); queue.push(1, 10); queue.peek(); // 1
Gets the priority of the key with the smallest priority, but does not remove the item from the queue.
const queue = new Heapify(); queue.push(1, 10); queue.peekPriority(); // 10
Removes the smallest priority item from the queue, returning its key.
const queue = new Heapify(); queue.push(1, 10); queue.pop(); // 1
Adds a new item to the queue with a given
priority. Will throw an error if the queue is already at its capacity.
const queue = new Heapify(); queue.push(1, 10); queue.length; // 1 queue.peek(); // 1 queue.peekPriority(); // 10
Returns a string with an array representation of all priorities in the queue. For instance, given the following priority heap:
10 30 20 40
The returned string will be
[10 30 20 40]. See tests for more examples.