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.

For more information about the Fibonacci heap, you can head here.

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);

Members

#.size

Methods

Mutation

#.push
#.pop
#.clear

Read

#.peek

#.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

#.clear

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