A JavaScript implementation of the binary heap data structure.
- 100% test coverage
- Supports all common heap operations*
- Store keys with optional associated values
- Optional custom compare function that can utilize both key and value to give full control over the order of the data
* except delete and decrease key
npm install --save @tyriar/binary-heap// Import npm module
var BinaryHeap = require('@tyriar/binary-heap';
// Construct BinaryHeap
var heap = new BinaryHeap();
// Insert keys only
heap.insert(3);
heap.insert(7);
// Insert keys and values
heap.insert(8, {foo: 'bar'});
heap.insert(1, {foo: 'baz'});
// Extract all nodes in order
while (!heap.isEmpty()) {
var node = heap.extractMinimum();
console.log('key: ' + node.key + ', value: ' + node.value);
}
// > key: 1, value: [object Object]
// > key: 3, value: undefined
// > key: 7, value: undefined
// > key: 8, value: [object Object]
// Construct custom compare BinaryHeap
heap = new BinaryHeap(function (a, b) {
return (a.key + a.value).localeCompare(b.key + b.value);
});
heap.insert('2', 'B');
heap.insert('1', 'a');
heap.insert('1', 'A');
heap.insert('2', 'b');
// Extract all nodes in order
while (!heap.isEmpty()) {
var node = heap.extractMinimum();
console.log('key: ' + node.key + ', value: ' + node.value);
}
// > key: 1, value: a
// > key: 1, value: A
// > key: 2, value: b
// > key: 2, value: B| Operation | Complexity |
|---|---|
| buildHeap | Θ(n) |
| clear | Θ(1) |
| extractMinimum | Θ(log n) |
| findMinimum | Θ(1) |
| insert | Θ(log n) |
| isEmpty | Θ(1) |
| size | Θ(1) |
| union | Θ(n) |
Creates a binary heap.
Parameters
customComparefunction An optional custom node comparison function.
Builds a heap with the provided keys and values, this will discard the heap's current data.
Parameters
keysArray An array of keys.valuesArray An array of values. This must be the same size as the key array.
Clears the heap's data, making it an empty heap.
Extracts and returns the minimum node from the heap.
Returns Node node The heap's minimum node or undefined if the heap is empty.
Returns the minimum node from the heap.
Returns Node node The heap's minimum node or undefined if the heap is empty.
Inserts a new key-value pair into the heap.
Parameters
keyObject The key to insert.valueObject The value to insert.
Returns Node node The inserted node.
Returns boolean Whether the heap is empty.
Returns number The size of the heap.
Joins another heap to this one.
Parameters
otherHeapBinaryHeap The other heap.
Creates a node.
Parameters
keyObject The key of the new node.valueObject The value of the new node.