Fibonacci Heaps and the Amortised Case for Decrease-Key

The Fibonacci heap exists to make one operation cheap: lowering the key of an element already in the queue. Every other operation is at least as expensive as in a binomial queue, and extraction is worse by a constant factor. The trade is deliberate and narrow. It pays off only in algorithms whose running time is dominated by decrease-key calls — Dijkstra’s algorithm on a graph with many more edges than vertices, Prim’s algorithm, and a family of network optimisation procedures — and the payoff is a logarithmic factor in the asymptotic bound, not a faster program.

The three structural decisions

A Fibonacci heap is a forest of heap-ordered trees with three properties that distinguish it from a binomial queue.

The trees are unordered with respect to size. Where a binomial queue maintains exactly one tree per order, a Fibonacci heap allows any number of trees of any size, and the root list is a circular doubly linked list with no order at all. This is what makes melding O(1): concatenating two circular lists is four pointer assignments, regardless of how many trees each contains.

Nodes carry a rank (the number of children) and a mark bit. The mark bit records whether a node has lost a child since it was last made a child of something else. It is the mechanism that bounds the damage from repeated cuts, and it is the structure’s central idea.

Consolidation is deferred. After an extraction, the root list is rebuilt so that no two trees share a rank, but the rebuild happens only during extraction, not during insertion or melding. A sequence of insertions produces a root list of n single-node trees, and the cost of cleaning that up is paid once, at the first extraction.

typedef struct fnode {
    int key, rank;
    int mark;                 /* 1 if this node lost a child since becoming a child */
    struct fnode *parent, *child;
    struct fnode *left, *right;   /* circular sibling list */
} fnode;

Each node holds four pointers plus three integers — seven words, against four for a pairing heap and one for an array heap. On a 64-bit build that is 56 bytes per element, so the structure occupies tens of megabytes for a million elements, and the access pattern is pure pointer chasing.

Decrease-key, cut, and the cascading rule

Lowering a key in place can violate the heap property only against the node’s parent, since the node’s children are unaffected and its parent’s key may now be larger. The repair has two cases.

If the node is a root, or if the new key is still no smaller than its parent’s, nothing happens. The decrease is complete in O(1).

Otherwise the node is cut: unlink it from its parent’s child list and from its siblings, add it to the root list, and clear its mark. The subtree it roots remains a valid heap. Its former parent now has one fewer child, and the parent’s own state decides what happens next. A root that loses a child is left alone, since the rank bound is needed only for non-roots. A non-root parent that was unmarked is marked, recording that it has lost a child. A non-root parent that was already marked is cut as well, recursively, and its parent is examined by the same rule.

That recursion is the cascading cut, and the mark bit is what bounds it. A node can lose at most one child while unmarked; the second loss triggers its own removal from its parent, which counts as a loss for that parent. The consequence is that a node of rank k has lost at most one child per marked episode, so its subtree holds at least F_(k+2) nodes, where F is the Fibonacci sequence — hence the name. Since the Fibonacci numbers grow as φ^k with φ ≈ 1.618, a rank of k implies a subtree of at least about 1.618^k nodes, so the maximum rank in a heap of n nodes is O(log n), specifically at most about log_φ n. For n = 10⁶ that is roughly 29; for 10⁹, roughly 43.

The amortised cost of decrease-key is O(1). A plain cut costs O(1) and increases the number of trees in the root list by one, which the potential function — the number of trees plus twice the number of marked nodes — charges for exactly; at the same time it may remove a mark from the cut node, worth −2. A cascading cut does both: it turns a marked node into a new root, adding one tree and clearing that mark, and it may mark the parent, adding two. The net potential change over a cascade is therefore at most +2, however many nodes it touches, and the O(1) charge per decrease-key pays for it. Only the single mark that can be left behind at the end of a cascade must be paid for by a later operation, and each such mark is cleared at most once, so the total is bounded by the number of decrease-key calls. The potential argument is what converts an operation with an unbounded worst case into a constant amortised one.

Consolidation and the extraction bound

Extraction is where the deferred work lands. Remove the minimum root, promote its children to the root list, then consolidate: repeatedly take two trees of the same rank and link them, until every rank appears at most once.

The consolidation uses an array of size proportional to the maximum possible rank, ⌊log_φ n⌋ + 1. Scan the root list; for each tree of rank r, if slot r is empty, place it there; otherwise link it with the tree already in the slot — the larger root becomes a child of the smaller, rank increments by one — and continue with the result. Because linking increases rank by exactly one, the process is the same carry chain as binary addition, and it terminates after O(log n) steps per tree. Total consolidation cost is O(log n) amortised per extraction, since the number of trees before consolidation is bounded by the potential and the number after is at most log_φ n + 1.

The array of slots is the one place the structure uses index arithmetic, and it is a stack-allocated array of pointers sized by the key width — about 46 entries for 32-bit keys and 92 for 64-bit ones, independent of n. Implementations that must handle either size compute the bound at run time from the key width, and the sizing must use the golden-ratio logarithm rather than the binary one, because the rank bound is derived from F_(k+2), not from 2^k; with the binary logarithm the array is too small and the link loop runs off its end. The derivation also assumes each node has lost at most one child, which the mark rule guarantees, so the bound holds for any sequence of operations and does not need a cap.

Why the bound does not translate into speed

The Fibonacci heap’s asymptotic advantages are real and were decisive in the analysis of network algorithms. The constant factors are not competitive, for reasons that are structural rather than accidental.

Pointer count and allocation. Seven words per node, allocated individually, with no contiguity. Every operation that touches a node follows a pointer into a region of memory determined by allocation history. A single decrease-key touches the node, its parent, its siblings’ links, and the root list — five or six distinct cache lines, each likely a miss. An array heap’s decrease-key with a position map touches two arrays at one index. The asymptotic difference is log n versus 1; the memory difference runs the other way, and for n below some threshold the array heap wins outright.

The rank bookkeeping is on the hot path. Every link during consolidation increments a rank and writes a child pointer; every cut adjusts a parent’s rank. These are arithmetic operations on fields that share cache lines with the keys, so they are not free, and they exist solely to support the analysis.

Cascading cuts make the worst case bad. A single decrease-key can cascade arbitrarily far up a tree, cutting every marked ancestor. The amortised bound is constant, but the distribution is heavy- tailed, which is exactly the wrong shape for a system with per-operation deadlines or a real-time constraint. The structure’s guarantees are about totals, not about individual calls.

Extraction is slower than a binary heap’s. Consolidation visits every root and performs links, and the constant is larger than an array heap’s sift-down, which touches one path. The claim that Fibonacci heaps improve Dijkstra’s complexity from O(m log n) to O(m + n log n) is a statement about the exponent structure, not about wall time.

Choosing against the analysis

The honest summary is that Fibonacci heaps are a theoretical instrument with narrow practical use. The cases where they are defensible are those where the operation counts are large, the graph is dense, and the implementation is tuned: a Dijkstra run on a graph where m is close to n² performs m decrease-keys and only n extractions, and the ratio is what the structure exploits.

For most workloads the decision goes the other way, and the alternatives in this cluster cover the range. The array heap with a position map is the default, as indexed binary heaps describes, because its constants are small and its memory is compact. A pairing heap gets constant-time meld and worst-case constant decrease-key with a smaller node, as pairing heaps sets out. A binomial queue keeps a logarithmic worst case with simpler code, per binomial queues.

What survives from the Fibonacci heap into everyday practice is the technique rather than the structure. Deferring work until it must be done, and charging it against a potential that measures disorder, is the pattern behind several later designs. The mark bit’s role — bounding how much a node can degrade before it is detached — reappears in structures that maintain relaxed balance. And the golden-ratio rank bound is a standard example of why the Fibonacci numbers appear in the analysis of algorithms that allow one unit of slack per level.