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