A TypeScript implementation of the Fibonacci 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
npm install --save @tyriar/fibonacci-heapSee the typings file for the full API.
// Import npm module
import { FibonacciHeap } from '@tyriar/fibonacci-heap';
// Construct FibonacciHeap
const heap = new FibonacciHeap<number, any>();
// 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()) {
const 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 FibonacciHeap
const heap2 = new FibonacciHeap<string, string>(function (a, b) {
return (a.key + a.value).localeCompare(b.key + b.value);
});
heap2.insert('2', 'B');
heap2.insert('1', 'a');
heap2.insert('1', 'A');
heap2.insert('2', 'b');
// Extract all nodes in order
while (!heap2.isEmpty()) {
const node = heap2.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 |
|---|---|
| clear | Θ(1)* |
| decreaseKey | Θ(1)* |
| delete | O(log n)* |
| extractMinimum | O(log n)* |
| findMinimum | Θ(1) |
| insert | Θ(1) |
| isEmpty | Θ(1) |
| size | Θ(n) |
| union | Θ(1) |
* amortized