Fibonacci Heap

Fibonacci heap is an amortized mergeable priority queue data structure within computation and algorithms that supports Insert, Find-Min, Meld (union), and Decrease-Key in O(1) amortized time, while performing Extract-Min and Delete in O(log n) amortized time. Invented by Michael L. Fredman and Robert Endre Tarjan in 1984 (and published in the Journal of the ACM in 1987), the structure derives its name from the Fibonacci numbers F_k, which arise as the lower bound on the number of nodes in a heap-ordered tree of degree k under the cascading-cut invariant, ensuring that the maximum degree of any node in an n-node Fibonacci heap never exceeds ⌊log_φ n⌋ ≈ 1.4404 log₂ n, where φ = (1 + √5) / 2 ≈ 1.61803 is the golden ratio.

By deferring structural consolidation until an Extract-Min operation is requested and allowing at most one child to be severed from any non-root node before triggering a cascading cut up the ancestor chain, a Fibonacci heap removes the O(log V) bottleneck of Decrease-Key in classical graph optimization. Substituting a Fibonacci heap for a binary heap reduces the asymptotic time complexity of Dijkstra's algorithm and Prim's algorithm from O((V + E) log V) to O(E + V log V), and improves Johnson's algorithm and the Stoer–Wagner algorithm to O(V² log V + VE).

Circular Doubly Linked Root List and Node Pointers

Whereas a binomial heap enforces the invariant that at most one binomial tree of each degree k exists after every single operation, a Fibonacci heap relaxes this structure into a forest of heap-ordered multiway trees whose roots are linked in an unordered circular doubly linked root list, accompanied by a direct pointer min[H] to the root containing the minimum key. Each node x stores:

• A pointer to its parent p[x] and a pointer child[x] to any one of its children (all sibling children of x are linked together in their own circular doubly linked list).
• Its child count degree[x] (the number of direct children of x).
• A Boolean flag mark[x] ∈ {true, false}, which records whether x has lost a child since the last time x was made a child of another node.

Because circular doubly linked lists support O(1) insertion, splicing, and removal:

• Insert(H, x): Places x as a new single-node tree into the root list of H and updates min[H] if key[x] < key[min[H]] in O(1) actual and amortized time.
• Meld(H1, H2): Concatenates the circular root lists of H₁ and H₂ and keeps the smaller min pointer in O(1) actual and amortized time.

Delayed Tree Linking During Extract-Min

When Extract-Min(H) is called, the minimum root z = min[H] is removed from the root list, and each of its degree[z] children is promoted directly into the root list. To prevent the root list from staying at linear length across repeated extractions, Extract-Min then executes a Consolidate(H) pass using an auxiliary degree-indexed pointer array A[0 .. D(n)]:

1. Iterate through every root w currently in the root list.
2. While another root y = A[d] already occupies slot d = degree[w], link the root with the larger key as a child of the root with the smaller key (clearing mark on the new child and incrementing degree of the winning root to d + 1), clear A[d], and repeat for degree d + 1.
3. Once Consolidate finishes, at most one root of each degree 0 ≤ d ≤ D(n) remains in the root list, and scanning those ≤ D(n) + 1 roots identifies the new min[H].

Marking and Cascading Cuts

To decrease the key of a node x to a new value k ≤ key[x] in O(1) amortized time, Decrease-Key(H, x, k) updates key[x] ← k. If x is a root or key[x] ≥ key[p[x]], the min-heap invariant remains intact and nothing further is done. If key[x] < key[p[x]], the heap invariant between x and its parent y = p[x] is violated, and the algorithm executes:

1. Cut(H, x, y): Detach x from the child list of y, decrement degree[y], add x to the root list of H, set p[x] ← nil, and reset mark[x] ← false.
2. Cascading-Cut(H, y): If y is not a root, check mark[y]:
   • If mark[y] == false (meaning x is the first child y has lost since y became a child of its own parent), set mark[y] ← true and halt.
   • If mark[y] == true (meaning y had already lost one child previously and has now lost a second child), call Cut(H, y, p[y]) and recursively call Cascading-Cut(H, p[y]) up the ancestor path until reaching either a root or an unmarked ancestor.

Potential Function and Fibonacci Subtree Size Proof

Let t(H) denote the number of trees in the root list of H and let m(H) denote the number of marked nodes in H. Fredman and Tarjan define the potential function:

Suppose a Decrease-Key call triggers a cascade of c cuts. The actual cost of the operation is O(c). However, the c cuts add c new trees to the root list (Δt = +c), clear the mark bits on the c − 1marked ancestors that were cut, and set at most 1 new mark bit on the final ancestor where the cascade stops (Δm ≤ −(c − 1) + 1 = −c + 2). Thus the change in potential is ΔΦ = c + 2(−c + 2) = 4 − c, and the amortized cost is:

Why does the two-strike marking rule bound the maximum degree D(n) to O(log n)? Let x be any node with degree[x] = k, and order its current children y₁, y₂, …, y_k in the chronological order in which they were linked to x. When y_i was linked to x during Consolidate, degree[y_i] equaled degree[x], which was at least i − 1 because y₁, …, y_i−1 were already children of x. Since that link occurred, y_i can have lost at most one child (otherwise a second lost child would have triggered a cascading cut that detached y_i from x). Therefore degree[y_i] ≥ i − 2 for all i ≥ 2.

Let s_k denote the minimum possible number of nodes in any subtree rooted at a node of degree k. Summing the root x, child y₁ (size ≥ 1), and children y₂, …, y_k yields the Fibonacci recurrence:

where F_k+2 is the (k + 2)-nd Fibonacci number and φ = (1 + √5) / 2. Since n ≥ s_k ≥ φ^k, taking logarithms base φ establishes D(n) ≤ ⌊log_φ n⌋.

Optimality in Comparison-Based Sorting and Graph Theory

The amortized bounds of a Fibonacci heap are asymptotically optimal under the comparison model: if both Insert and Extract-Min ran in o(log n) amortized time, inserting n elements and extracting them in sorted order would sort n elements in o(n log n) comparisons, violating the information-theoretic Ω(n log n) comparison-sorting lower bound. In theoretical graph algorithms, any algorithm performing V minimum extractions and E key reductions achieves O(E + V log V) runtime with a Fibonacci heap, which is linear in E whenever E ≥ V log V.

Constant Factors, Cache Locality, and Practical Alternatives

Despite its landmark asymptotic bounds, a standard Fibonacci heap stores four pointers (parent, child, left, right), an integer degree, and a mark bit in every node, and its circular doubly linked list manipulations incur frequent pointer chases across non-contiguous memory. Moreover, on typical real-world networks (such as road networks or planar meshes), the vast majority of edge relaxations in Dijkstra's algorithm do not improve the current tentative distance, so the actual number of Decrease-Key calls is much smaller than E. Consequently, contiguous-array d-ary heaps (d = 4 or 8), hollow heaps, or two-pointer pairing heaps usually outperform Fibonacci heaps in wall-clock execution time while retaining simpler code.

What would go wrong if a Fibonacci heap simply cut every decreased node to the root list without cascading cuts?

If Decrease-Key severed a child x from its parent y without ever cutting y when y lost multiple children, an adversary could link two roots into a tree of degree k and then repeatedly cut all k − 1 grandchildren, leaving a root of degree k that contains only k + 1 nodes instead of ≥ φ^k nodes. During a subsequent Extract-Min, the root could have degree D(n) = Θ(n), degrading Extract-Min from O(log n) amortized time back to Θ(n).

Why is the potential multiplier on marked nodes equal to 2 instead of 1 in Φ(H) = t(H) + 2 m(H)?

When a marked ancestor y loses its second child during a cascading cut, Cut(H, y, p[y]) clears mark[y] (reducing m(H) by 1) but simultaneously moves y into the root list (increasing t(H) by 1). Multiplying m(H) by 2 ensures that clearing mark[y] releases two units of potential: one unit pays for the new root added to t(H) for future consolidation, and the second unit pays for the actual O(1) pointer work of cutting y during the current Decrease-Key call.

Are there priority queues that achieve Fibonacci heap bounds in the worst case rather than only in the amortized sense?

Yes. Gerth Stølting Brodal (1996) constructed the Brodal queue, which achieves O(1) worst-case time for Find-Min, Insert, Meld, and Decrease-Key and O(log n) worst-case time for Extract-Min, and Brodal, Lagogiannis, and Tarjan (2012) later simplified this to the strict Fibonacci heap using pointer-based structural invariants without auxiliary arrays.

1. Fredman, M. L., & Tarjan, R. E. (1987). "Fibonacci heaps and their uses in improved network optimization algorithms." Journal of the ACM, 34(3), 596–615 (preliminary version in FOCS 1984, 338–346). https://doi.org/10.1145/28869.28874
2. Brodal, G. S. (1996). "Worst-case efficient priority queues." In Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '96), 52–58. https://dl.acm.org/doi/10.5555/313852.313883
3. Brodal, G. S., Lagogiannis, G., & Tarjan, R. E. (2012). "Strict Fibonacci heaps." In Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing (STOC '12), 1177–1184. https://doi.org/10.1145/2213977.2214082
4. Kaplan, H., Kozma, L., Zamir, O., & Zwick, U. (2017). "Hollow heaps." ACM Transactions on Algorithms, 13(4), Article 52. https://doi.org/10.1145/3093240