The Fibonacci Heap

A Fibonacci heap is a collection of heap-ordered trees whose roots sit in a circular doubly linked list, with one pointer to the root holding the minimum key. Unlike a binomial heap, the trees carry no shape invariant between operations: any number of trees of any degree may coexist.

The design principle is deferral. Insert, meld, and decrease-key perform the least work that leaves the heap correct — a pointer splice — and never restructure. The accumulated disorder is cleaned up by extract-min, the one operation that must inspect the roots anyway. Every bound in the structure is amortized; individual operations can be much more expensive than their stated cost.

Insertion creates a single-node tree, splices it into the root list, and updates the minimum pointer if the new key is smaller. No comparison chain, no linking, no carry: the cost is O(1) worst-case. A heap built by n insertions is a root list of n singleton trees, which is a valid Fibonacci heap.

Melding two heaps concatenates their root lists and takes the smaller of the two minimum pointers, also O(1) worst-case. This is the operation binomial heaps perform in O(log n) and array-backed heaps in O(n). find-min reads the minimum pointer in O(1).

Extract-min removes the minimum root and promotes each of its children to the root list, since each child subtree is already heap-ordered. The root list is then consolidated: process the roots with an array indexed by degree, and whenever two roots share a degree, link them by making the larger-keyed root a child of the smaller. The merged root's degree rises by one and may collide again.

Consolidation ends with at most one root per degree, so the root list shrinks to O(log n) entries, and a final scan sets the new minimum. The work is proportional to the root-list length plus the degree of the removed node, which can be Θ(n) after a long run of insertions. Amortized over a sequence it is O(log n), because that long root list was itself paid for by the cheap operations that built it.

Decrease-key lowers a node's key. If the node is a root, or its key still exceeds its parent's, nothing else is required. Otherwise heap order is restored by cutting: detach the node with its whole subtree, splice it into the root list as a new root, and clear its mark.

The cut costs O(1) and it does not restore any shape invariant — the former parent simply loses a child and its degree drops. That is the trade the structure makes. A binary heap restores its shape immediately and pays O(log n) per decrease-key; a Fibonacci heap defers, and the resulting damage to tree shape is bounded by a second mechanism rather than by repair.

Unlimited cutting would let a tree of high degree be stripped until its root's degree no longer certifies any subtree size, breaking the degree bound that extract-min relies on. Each non-root node therefore carries one mark bit, set when the node loses its first child since it last became a child of another node.

When a marked node loses a second child it is itself cut and moved to the root list, and its parent's mark is examined in turn: the cut cascades upward until it reaches an unmarked node, which becomes marked, or a root, which is never marked. A cascade can traverse many levels, but each level cut clears a mark, and marks are only created one per operation. The amortized cost of decrease-key stays O(1).

Because a node keeps at most two children fewer than it had when they were attached, the subtree sizes stay exponential in the degree. Number the children of a node x in the order they were linked: when the i-th child was linked, both it and x had degree i − 1, and it has lost at most one child since, so its degree is at least i − 2 now.

Solving the resulting recurrence gives a subtree of at least F_{k+2} nodes under a node of degree k, where F is the Fibonacci sequence — the source of the name. Since F_{k+2} ≥ φ^k with φ = (1+√5)/2 ≈ 1.618, the maximum degree is at most log_φ n ≈ 1.44 log₂ n. That bound is what makes the consolidation array a logarithmic-sized array.

The analysis uses the potential Φ = t + 2m, where t counts the trees in the root list and m counts the marked nodes. Insert adds one tree and pays one unit of potential, keeping its amortized cost O(1). Meld leaves both counts unchanged.

Extract-min does work proportional to the old t but drives t down to O(log n), so the released potential cancels the linking work and leaves O(log n) amortized. A cascading cut of c levels adds c trees and costs Θ(c), but it clears c − 1 marks, releasing 2(c − 1) potential; the net amortized cost is constant. The doubled weight on marks exists precisely so that this cancellation works.

The resulting bounds are O(1) amortized for insert, find-min, meld, and decrease-key, and O(log n) amortized for extract-min and delete. Insert, find-min, and meld are also O(1) in the worst case; decrease-key and extract-min are not.

A single decrease-key can cascade through Θ(log n) levels, and a single extract-min after n insertions consolidates Θ(n) roots. Systems with per-operation latency budgets cannot use these bounds directly. Later designs — strict Fibonacci heaps and Brodal queues — recover the same bounds in the worst case, at the cost of substantially more bookkeeping.

Dijkstra's algorithm performs n extract-min operations and up to m decrease-key operations. With a binary heap both cost O(log n), giving O(m log n). With a Fibonacci heap the decrease-keys become O(1) amortized and the total falls to O(m + n log n), which is asymptotically better on dense graphs where m approaches n².

Fredman and Tarjan introduced the structure for exactly this purpose in 1984, and applied it to Prim's minimum spanning tree algorithm and to their own O(m β(m, n)) MST algorithm. The bound is still the standard statement of Dijkstra's complexity in the literature, which means the structure's main footprint is in the analysis of algorithms rather than in their implementations.

A Fibonacci heap node stores a key, parent, child, and two sibling pointers, a degree, and a mark bit — roughly 48 bytes of overhead per element on a 64-bit machine, against zero for an array-backed heap. Every operation dereferences several of those pointers, and the nodes are wherever the allocator put them.

Consolidation walks a root list that may hold thousands of scattered nodes in the same pass. The result is that measured running times often exceed those of a four-ary heap on the same workload despite the better bounds, since the O(1) decrease-key hides a constant several times the cost of a cached array swap. The Boost Graph Library changed the default queue for dijkstra_shortest_paths to a four-ary d_ary_heap_indirect after measuring it roughly 23% faster than the relaxed-heap alternative on its Dijkstra benchmark.

Choose a Fibonacci heap when decrease-key dominates the operation mix, the graph or workload is dense enough that the asymptotic gap is real, and the amortized bound is acceptable — batch computations rather than latency-bound services. The O(1) meld also matters when many queues are combined.

Otherwise the costs dominate: six fields per node, one allocation per element, poor locality, and an implementation long enough that correctness depends on the mark discipline being exactly right. A pairing heap gives most of the practical benefit with a fraction of the code, and a d-ary binary heap with lazy deletion is usually faster still on sparse graphs.

The sources reviewed for this chapter do not identify a prominent production system that runs a Fibonacci heap on a hot path. Where the structure appears in shipped software it is as an option rather than a default: Boost.Heap provides boost::heap::fibonacci_heap with mutable handles, LEDA provides a Fibonacci heap among its priority queue implementations, and the GNU C++ policy-based data structures include thin_heap_tag, Tarjan's thin heap, which reproduces the Fibonacci bounds with a simpler node record.

The measured picture explains the gap. Empirical comparisons of priority queues under Dijkstra's algorithm — including the University of Texas study by Chen, Chowdhury, Ramachandran, Roche, and Tong — report that simpler structures generally beat Fibonacci heaps on real graphs, and the Boost Graph Library's default queue is a four-ary heap rather than a Fibonacci or relaxed heap for that reason. The structure's durable contribution is the amortized O(m + n log n) bound for Dijkstra and Prim, which remains the reference result those implementations are measured against.

A Fibonacci heap keeps a root list of heap-ordered trees and defers all restructuring to extract-min. Insert, meld, and decrease-key are pointer splices; consolidation rebuilds one tree per degree; and cascading cuts, driven by one mark bit per node, keep subtree sizes exponential in degree so that the maximum degree stays below 1.44 log₂ n.

Insert, find-min, meld, and decrease-key are O(1) amortized; extract-min and delete are O(log n) amortized. Nothing is guaranteed per operation, and the per-node overhead is roughly 48 bytes with pointer-chasing access throughout. The structure buys an asymptotic improvement in graph algorithms that its constants often prevent from appearing in a measurement.