Fibonacci heap
Invented by  Fredman, Tarjan (1987)  

Idea: 
 
Advantages: 
 
Disadvantages:  in practice, it is usually outperformed by simpler heaps  
Note:  the data structure has been deamortized (i.e., even more complicated data structure is known which guarantees the same time bounds, but in worst case) 
Motivation
Fibonacci heap was motivated by the question: Is there a heap where decreasekey
takes less than logarithmic time (while all the other operations still take at most \(O(\log n)\) time)? In lazy binomial heap we “shifted” some of the work from merge
and insert
to the cleanup during extractmin
. Can we do something similar with decreasekey
? (The answer is YES.)
This might be interesting, because there are applications, where we decreasekey
“a lot”, and we insert
and extractmin
much less often. Specifically, in Dijkstra’s algorithm for finding the shortest path and JarníkPrim’s algorithm for finding the minimum spanning tree, we call decreasekey
potentially for every edge of the input graph, while insert
and extractmin
are called only once per every vertex.
merge 
insert 
extractmin 
decreasekey 


binomial heap  \(O(\log n)\)  \(O(\log n)\)  \(O(\log n)\)  \(O(\log n)\) 
lazy binomial heap  \(O(1)\)  \(O(1)\)  \(O(\log n)\) amortized  \(O(\log n)\) 
Fibonacci heap  \(O(1)\)  \(O(1)\)  \(O(\log n)\) amortized  \(O(1)\) amortized 
Cutting
The natural way to fix heap ordering after a key has been changed, is “bubbling”  we compare the key with its parent and if the parent is bigger, we swap them. This is the standard algorithm already used in ordinary binary heaps and binomial heaps. However, this process may continue all the way up to the root and thus take \(\Theta(\log n)\) time in the worst case.
Idea #1: When decreasing key of \(x\), we can cut the node from its parent and add the whole subtree to the list of trees. The heap will not consist of binomial trees any more, but of whatever remains after cutting some nodes. We define \(rank\) of a node to be the number of its children and during cleanup, we link trees with the same rank.
As we show below in the “But why?” section, it turns out this is not enough. The problem is that we could end up with small trees with high rank, i.e., many children. Recall that the proof that cleanup in lazy binomial heaps takes \(O(\log n)\) (amortized) time depends on
 the number of children is \(O(\log n)\) for each node, and
 there are at most \(O(\log n)\) trees after cleanup.
We need ranks to be bounded by \(O(\log n)\) and for that we need the size of the trees to be exponential in rank.
We will show that the following insane idea works:
Idea #2: We cut even more. When decreasing key, we cut the node from its parent and add the whole subtree to the list of trees. Furthermore, mark the parent that has lost a child. If a node loses two children, we also cut it, we add the subtree to the list of trees and mark its parent. This may start a cascade of cuts as in the figure below:
Fig. above: Black nodes have lost one child, white nodes have not and for grey nodes it’s irrelevant in this example. Decreasing the key in \(x\) leads to cutting \(x\) which leads to cutting \(a\) and \(b\) because both have already lost one child and marking node \(c\).
This looks crazy, but we will show that
 all the cutting takes just \(O(1)\) amortized time and
 it keeps the size of trees exponential in their rank.
Analysis
 We use the following invariant:
Invariant: Each marked node will have 2$
saved for future cuts. Also remember that each root needs to have 1$
saved for cleanup in future (see the proof for lazy binomial heaps).
Lemma: 4$
per decreasekey
is sufficient to pay for all the cascading cuts and keep the invariant.
Proof:
 we pay 1
$
for \(O(1)\) computation (cutting the node, adding it to the list of trees, marking the parent)  the node becomes a new root so we save 1
$
to restore the invariant  all the marked ancestors we cut already have 2
$
saved so they pay 1$
for the computation and keep 1$
(since they become new roots)  from the amortized point of view, these cascading cuts are “for free”  ultimately, we reach an unmarked parent, which we mark and deposit 2
$
to its account (to keep the invariant)
 To prove that each tree has exponential size in its rank, we first prove it has the following property:
Property: Fix a point in time. Let \(x\) be any node of \(rank(k)\), and let \(y_1,\ldots,y_k\) denote its current children in the order in which they were linked to \(x\). Then \(rank(y_i) \geq i2\).
Proof: At the time of linking \(y_i\) under \(x\), \(x\) had at least \(i1\) children (it still has these \(i1\) children \(y_1,\ldots,y_{i1}\)). But we only link two trees during cleanup, when they have the same rank. So at the time of linking, \(y_i\) also had rank at least \(i1\). Since then, \(y_i\) may have lost at most one child (if two children were lost, we would have cut \(y_i\)).
Note that this property holds for any node in Fibonacci heap  not just the root.
Theorem: Size of tree with rank \(k\) is exponential in \(k\).
Proof: Well, let’s try to find for each rank \(k\) the smallest possible tree (call it \(F_k\)) having the property above. Here are the first few trees with ranks 0 … 5:
Note that their sizes are 1, 2, 3, 5, 8, 13, …
How did we construct \(F_5\)?
\(F_5\) has a root with 5 children. According to the property above, ranks of the children are at least 0, 0, 1, 2, 3 (respectively) and we have already established the smallest trees for these ranks. So \(F_5\) consists of a root with subtrees \(F_0, F_0, F_1, F_2, F_3\). In general, we get the recurrence \(F_n = 1 + 1 + \sum_{i=0}^{n2} F_i\).
Alternatively, if we compare \(F_5\) to \(F_4\), we see that the root of \(F_5\) has just one more child and according to the property, the child’s rank is at least 3. Thus, \(F_5\) looks like \(F_4\) with an extra subtree \(F_3\):
This is where we get the familiar recurrence \(F_n = F_{n1} + F_{n2}\) for Fibonacci numbers.
It is easy to prove that \(F_n \geq \phi^n\) where \(\phi\approx 1.618...\) is the golden ratio.
But why?
The first time one learns about Fibonacci heaps, it looks insane. Why do we need to do the cascading cut?? It adds more work  first we cut more nodes and then later we have more nodes to clean up. Can’t we just cut a single node?
The answer is NO: It would break the proof that extractmin
takes \(O(\log n)\) time. We could have trees with big rank but only few nodes.
OK, so we would break that proof, but there could still be different one?
The answer is NO: If we didn’t do the cascading cuts, the structure could be slow, even in the amortized sense. Here is why.
Let \(S_k\) be a tree consisting of a root and \(k\) children:
…and let \(T_k\) be a tree consisting of a root with subtrees \(S_0,S_1,\ldots,S_{k1}\) as children:
Note that \(T_k\) has \(\Theta(k^2)\) nodes and can be constructed by \(O(k^3)\) heap operations. Also note that when we link \(S_k\) under \(T_k\), we get \(T_{k+1}\).
Let’s start with heap \(T_k\), where the root’s key is zero and the keys of its children are huge numbers (practically “\(\infty\)”). Now insert
a new node (bigger than root) and call extractmin
. This will remove the root, add the children to the list of roots and cleanup will link them one by one under the new node (\(S_0 + T_0 \to T_1\), \(S_1 + T_1 \to T_2\), etc.) and we end up with \(T_k\) again.
The cleanup takes \(\Theta(k)=\Theta(\sqrt n)\) time and we can repeat the operations as many times as we want  repeating the insert
and extractmin
cycle \(m\) times will take \(\Theta(m\times\sqrt n)\) so the complexity will be \(\Omega(\sqrt n)\) even in the amortized sense.
References
 M.L. Fredman and R.E. Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM (JACM), 34(3):596615, 1987. [bib]