Mnemonist

Fibonacci Heap

The Fibonacci heap is usually thought as an improvement over the classical Heap because some of its operations can run in an amortized constant time.

By default, the provided `FibonacciHeap` is a min heap and the `MaxFibonacciHeap` is just some sugar that will reverse the provided comparator for you.

``````const FibonacciHeap = require('mnemonist/fibonacci-heap');
// To access min/max fibonacci heap
const { MinFibonacciHeap } = require('mnemonist/fibonacci-heap');
const { MaxFibonacciHeap } = require('mnemonist/fibonacci-heap');

// To create a heap:
const heap = new FibonacciHeap();
``````

Constructor

The `FibonacciHeap` takes a single optional argument being the comparator function to be used to compare the given items.

``````// Providing a comparator to handle custom objects
const heap = new FibonacciHeap((a, b) => {
if (a.value < b.value)
return -1;
if (a.value > b.value)
return 1;
return 0;
});

heap.push({value: 34});
heap.push({value: 45});

heap.peek();
>>> 34
``````

Static #.from

Alternatively, one can build a `FibonacciHeap` from an arbitrary JavaScript iterable likewise:

``````const heap = FibonacciHeap.from([1, 2, 3], comparator);
``````

Methods

Mutation

#.size

Number of items in the heap.

``````const heap = new FibonacciHeap();
heap.size
>>> 0
``````

#.push

Pushes an item into the heap.

`O(1)`

``````const heap = new FibonacciHeap();
heap.push(34);
``````

#.pop

Retrieve & remove the min item of the heap (or the max item in case of a `MaxFibonacciHeap`).

`O(log n)`

``````const heap = new FibonacciHeap();

heap.push(4);
heap.push(34);
heap.push(5);

heap.pop();
>>> 4

heap.size
>>> 2
``````

Completely clears the heap.

``````const heap = new FibonacciHeap();

heap.push(34);
heap.clear();
heap.size
>>> 0
``````

#.peek

Retrieves the min item of the heap (or the max item in case of a `MaxFibonacciHeap`).

`O(1)`

``````const heap = new FibonacciHeap();

heap.push(4);
heap.push(34);
heap.push(5);

heap.peek();
>>> 4
``````