A Fibonacci Heap implementation in C++

# Fibonacci Heap

STL like implementation

The Fibonacci Heap is the famous data structure that allows to decrease the running time of Dijkstra’s algorithm from $O((V+E)\log V)$ to $O(V\log V + E)$ since it implements the `decrease_key`

operation in $\Theta(1)$ amortized time. It also support a set of operations that make it a “mergeable heap” (see mergeable heap).

To achieve such performance a fibonacci heap is basically a linked list of min-heap-ordered rooted trees (that are, in turn, implemented as linked list of smaller min-heap-ordered rooted tree). To implement the structure we first need to implement the template for a linked list (since it will be a linked list of fibonacci nodes that are not yet defined we need to use a template).

The linked list need to support just a few basic operations

`push_back`

append a node to the list`extract_node`

extract a specific node without modifying its pointers`remove_node`

completely remove a node by extracting it and clearing its pointers.`clear`

clears the list

Such list should look something like this.

Now it’s time to implement the fibonacci heap’s node. The nodes are the most important part of the whole structure.

As happens with any other nodes of a heap, a fibonacci heap’s node has key and data attributes and, since it’s a element of a linked list, it also has two pointer left and right that points to its neighbors. Each node could potentially be the root of a sub tree, for that reasons it need to store the number of its child, using the degree attribute. A boolean attribute mark it’s used to keep track if a node has lost a child.

Finally it comes the actual structure. A fibonacci heap has some utility method that are used by the other procedure, those are:

`consolidate`

rearrange the internal structure after the minimum element if extracted.`cut`

cut the link between a node x and its parent making x a root.`cascading_cut`

recursively cut nodes until it find a root or an unmarked node.`make_child`

takes two nodes and make one child of the other.`max_degree`

return the maximum number of nodes in the root list.

The public methods implemented below are the following (what they do is self explanatory):

`insert`

`extract_min`

both delete and return the element whose key is minimum`decrease_min`

other method that have not been implements but that could be useful are: union and delete.

To make decrease_key work in constant time it’s also necessary to get, in constant time, a node given its key. To do that I used a hash table (implemented with an unordered_map) to map each key to the address of its corresponding node.

Although the asymptotic running time for decrease_key is constant the structure itself is quite slow because of the complex internal structure that need to be updated. Such implementation uses template and it has been tested and should be bug free.

Here is the link on GitHub of the complete implementation: fibonacci heap