Fibonacci heap

Invented by	Fredman, Tarjan (1987)
Idea:	start with the lazy binomial heap and be even more lazy during decrease-key, instead of bubbling the node up, just cut the whole subtree and add to the list of trees however, for the consolidation phase to work properly, we need the number of nodes in a tree of order \(k\) to be still exponential in \(k\) thus, when cutting a node, mark its parent; when it is already marked, cut also the parent
Advantages:	it is theoretically optimal – extract-min is in \(O(\log n)\), all the other operations take \(O(1)\) time if there are more decrease-key than extract-min operations (as in Dijkstra’s or Jarník-Prim’s algorithm), this data structure gives asymptotically better time complexity
Disadvantages:	in practice, it is usually outperformed by simpler heaps
Note:	the data structure has been de-amortized (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 decrease-key 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 extract-min. Can we do something similar with decrease-key? (The answer is YES.)

This might be interesting, because there are applications, where we decrease-key “a lot”, and we insert and extract-min much less often. Specifically, in Dijkstra’s algorithm for finding the shortest path and Jarník-Prim’s algorithm for finding the minimum spanning tree, we call decrease-key potentially for every edge of the input graph, while insert and extract-min are called only once per every vertex.

	merge	insert	extract-min	decrease-key
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

1. the number of children is \(O(\log n)\) for each node, and
2. 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

1. all the cutting takes just \(O(1)\) amortized time and
2. it keeps the size of trees exponential in their rank.

Analysis

1. 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 decrease-key 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)

2. 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 i-2\).

Proof: At the time of linking \(y_i\) under \(x\), \(x\) had at least \(i-1\) children (it still has these \(i-1\) children \(y_1,\ldots,y_{i-1}\)). 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 \(i-1\). 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}^{n-2} |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_{n-1}| + |F_{n-2}|\) 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 extract-min 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_{k-1}\) 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 extract-min. 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 extract-min 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):596-615, 1987. [bib]