binaryheaps
v1.0.0
Published
binary heap with fast increaseKey and decreaseKey operations
Downloads
18
Readme
A binary heap, suppose heap has n elements
isEmpty - O(1)
decreaseKey - O(log(n))
increaseKey - O(log(n))
insert - O(log(n))
delete - O(log(n))
from - O(n)
extract - O(log(n))
peek - O(1)
The heap is implemented internally as a binary tree represented by an array, and a map we maintain allows us O(1) lookup of elements. As such it has a greater memory overhead, and slightly lengthier insert, extract, etc. with the trade off of O(log(n)) delete, increase and decrease operations.
You can use it like so
const PriorityQueue = require("binaryheaps");
const arr = [2, 3, 1, 5, 6];
const cmp = (a, b) => a >= b ? 1 : -1;
const p = PriorityQueue.from(arr, cmp);
const largest = p.extract();
console.log(largest) // 6
In general you can either call new PriorityQueue(cmp)
where cmp
is a function (a: T, b: T) => number
which returns 1 if a > b, 0 if a === b, else -1, where T
is the type of the elements inserted into your queue.
Alternatively you can use the static from
method as above which takes as its first argument an iterable.