Fibonacci Heap, in depth: lazy forests, the degree lemma, why cascading cuts matter, an invariant checker and measured costs

The shape: lazy trees, a min pointer and marks

The heap is a forest of heap-ordered trees: every node's key is at least its parent's. The roots sit on a circular doubly linked list, and a min pointer names the smallest root. Each node stores its key, a parent pointer, one child pointer, left and right siblings, its degree (number of children) and one bit, mark, meaning the node has lost a child since it last became a child itself.

The design principle is laziness. Insert and merge just splice lists, so the forest can hold many small trees. All tidying is deferred to extract-min, which links trees of equal degree until every root degree is distinct. Decrease-key also refuses to restructure: it cuts the node out and makes it a root.

The five operations

• insert(k): make a one-node tree and splice it into the root list; update min. O(1).
• merge(H1, H2): splice the two circular root lists in O(1) and keep the smaller min. Binary heaps need O(n) for this, which is the main reason mergeable heaps exist.
• extract-min: remove the min root, move its children to the root list, then consolidate: walk the roots with an array indexed by degree, and whenever two roots share a degree, link the larger-keyed one under the other and retry at degree + 1. Finally rebuild the root list and min from the array.
• decrease-key(x, k): lower the key. If heap order with the parent breaks, cut x to the root list and clear its mark. Then walk up: an unmarked parent becomes marked and the walk stops; a marked parent is cut too and the walk continues. Roots are never marked.
• delete(x): decrease-key to minus infinity, then extract-min.

A small consolidation trace. Insert 5, 9, 2, 7, 4 and 8: six one-node roots, min 2. extract-min removes 2; suppose it then walks the other roots in the order 5, 9, 7, 4, 8 (the real order depends on how the list was spliced). Root 5 takes slot 0. Root 9 also has degree 0, so it is linked under 5, which moves to slot 1. Root 7 takes slot 0. Root 4 collides with 7 in slot 0, so 7 goes under 4; 4 now has degree 1 and collides with 5 in slot 1, so 5 (with its child 9) goes under 4, which lands in slot 2. Root 8 takes slot 0. The result is two roots, 8 and 4, with degrees 0 and 2, and the new min is 4. Five pending roots became two trees in one pass. Another walk order builds different trees (the code above, run on these keys, ends with roots 4 and 5), but always with distinct root degrees.

The degree lemma, and where the name comes from

Everything rests on one lemma: a node of degree k roots a subtree with at least F(k+2) nodes, where F is the Fibonacci sequence 1, 1, 2, 3, 5, 8, ... Since F(k+2) ≥ φ^k with φ = 1.618..., the maximum degree D(n) is at most ⌊log_φ n⌋ ≈ 1.44 log2 n. This is where the name comes from.

The proof has two steps. First, order x's current children by when they were linked under x: y1, y2, ..., yk. When yi was linked, x already had at least y1..y(i-1), so its degree was at least i-1, and consolidation only links equal degrees, so yi had degree at least i-1 too. Since then yi may have lost at most one child, because a second loss would have cut it away from x. So yi has degree at least i-2.

Second, let s(k) be the minimum size of a subtree whose root has degree k. Then s(k) ≥ 2 + sum over i from 2 to k of s(i-2), counting x, y1, and the subtrees of y2..yk. The same recurrence defines F(k+2), so s(k) ≥ F(k+2).

The mark bit is exactly the bookkeeping for "lost at most one child". Measured on a heap left with 166,666 nodes after 200,000 inserts and a mix of 33,334 extract-mins and up to 100,000 random decrease-keys, the largest degree was 17 against a bound of log_φ n = 25.0, and the smallest subtree of each degree was never below F(k+2): degrees 0 to 3 met the bound exactly (1, 2, 3 and 5 nodes), degree 4 had at least 9 nodes (bound 8), degree 8 at least 182 (bound 55).

Paying for laziness: the amortized costs

The amortized bounds come from the potential Φ = t + 2m, where t is the number of trees on the root list and m the number of marked nodes. Measure actual cost in units of pointer work and charge each operation its actual cost plus the change in Φ.

• insert does O(1) work and adds one tree: amortized O(1). merge does O(1) work and Φ of the union is the sum: O(1).
• extract-min adds at most D(n) children to the root list, then consolidation does work proportional to the number of roots, t + D(n). Afterwards at most D(n) + 1 roots remain, so Φ falls by about t - D(n), which pays for the t part. Amortized cost is O(D(n)) = O(log n).
• decrease-key with c cascading cuts does O(c) work. It adds c trees, but each of the c - 1 cascaded cuts clears a mark, worth 2 units, and at most one new mark is set. The net change in Φ is at most c - 2(c - 1) + 2 = 4 - c, so the amortized cost is O(1) no matter how long the cascade.

This is why the marks are weighted twice: one unit pays for the cut, the other for the extra root it creates. The arithmetic is spelled out step by step in the potential method.

What breaks without cascading cuts

Drop the cascading cut and the lemma fails. To see it, insert keys 0 to 4,096, call extract-min once (consolidation turns the 4,096 survivors into a single binomial tree of degree 12), then take every node at depth two or more, decrease it below everything and extract it.

Without cascading cuts the root keeps all 12 children, and each child has lost all of its own: the result is a star of degree 12 with 13 nodes, where the lemma demands F(14) = 377. With cascading cuts the same sequence left 13 nodes whose largest degree was 4, in a tree of 11 nodes. Scale the construction up and star-shaped roots keep a degree linear in their size, so extract-min can be forced to move Θ(n) children and the O(log n) amortized bound is gone.

Consolidate, decrease-key and an invariant checker

The core of an implementation is consolidate and the cut pair. The three functions below, exactly as shown, were bound onto a heap class and fuzzed against a reference model in 300 runs of 400 random operations each, with the checker run after every operation.

def _consolidate(self):
    roots, r = [], self.min
    while True:                      # snapshot first: linking edits the list
        roots.append(r); r = r.right
        if r is self.min: break
    table = [None] * (int(math.log(self.n, PHI)) + 3)
    for x in roots:
        _unlink(x)
        d = x.degree
        while table[d] is not None:  # two roots of equal degree: link them
            y = table[d]
            if y.key < x.key:
                x, y = y, x
            self._link(y, x)         # y becomes a child of x, x.degree += 1
            table[d] = None
            d += 1
        table[d] = x
    self.min = None
    for x in table:
        if x is not None:
            self._add_root(x)        # clears parent and mark, updates min

def decrease_key(self, x, k):
    if k > x.key:
        raise ValueError("new key is larger")
    x.key = k
    p = x.parent
    if p is not None and x.key < p.key:
        self._cut(x, p)              # move x to the root list
        while p.parent is not None:  # cascading cut
            if not p.mark:
                p.mark = True
                break
            gp = p.parent
            self._cut(p, gp)
            p = gp
    if x.key < self.min.key:
        self.min = x

def check(h):
    """Heap order, sibling links, parent links, degree fields, size and min."""
    seen = 0
    def walk(first, parent):
        nonlocal seen
        out, x = [], first
        while first is not None:
            assert x.parent is parent and x.right.left is x
            assert parent is None or parent.key <= x.key
            assert len(walk(x.child, x)) == x.degree
            seen += 1; out.append(x); x = x.right
            if x is first: break
        return out
    roots = walk(h.min, None)
    assert seen == h.n
    assert not roots or h.min.key == min(r.key for r in roots)

The table is sized from the degree bound plus slack. Taking the snapshot before linking avoids the classic bug of iterating a circular list while you splice nodes out of it.

Measured against a binary heap

heapq is implemented in C, so the first row mostly measures interpreter overhead, but the shape holds in compiled languages too: a binary heap is one contiguous array and a Fibonacci heap is pointer-chasing over nodes with six fields. In the decrease-key-heavy row the lazy binary heap simply pushes a duplicate entry and skips stale ones on pop, and it still won. The asymptotic gain appears only when decrease-keys vastly outnumber extract-mins on large inputs, as in dense graphs.

Operational guidance

• Default to a binary or d-ary heap. Reach for a Fibonacci heap when you need O(1) merge, or when profiling shows decrease-key dominating on large dense inputs. Boost.Heap ships fibonacci_heap, pairing_heap and d_ary_heap behind one interface, which makes measuring cheap.
• Keep handles. decrease-key needs a pointer to the node, so insert returns a handle the caller stores, typically in an array indexed by item id.
• Pool the nodes. Allocate nodes from an arena; per-node allocation dominates the cost in C++ and Rust.
• Run the checker in tests. Call check after every operation in debug builds and fuzz against a sorted list or heapq model.

Failure modes

• Forgetting to clear marks when a node becomes a root or is linked under another root; stale marks trigger needless cuts and break the potential.
• Iterating the root list while consolidating it, which skips or revisits roots.
• Updating parent.child wrongly on a cut: if the cut node was the child pointer, move it to a sibling, or to None when it was the only child.
• Undersized degree table: size it from log_φ n plus slack, or grow it.
• Recursive traversal in checkers or destructors overflowing the stack on degenerate shapes.
• Comparing equal keys inconsistently between extract-min and decrease-key, which makes ties nondeterministic; add a sequence number if order matters.

Trade-offs

What to do next

1. Implement insert, merge, extract-min, decrease-key and delete with the checker, and fuzz against a model for a few hundred random runs.
2. Reproduce the no-cascade experiment and confirm the star of degree 12.
3. Log the maximum degree on your workload and compare it with log_φ n.
4. Benchmark against a binary heap with lazy deletion before adopting it; see the indexed binary heap and leftist heaps for the alternatives.
5. Work through the potential method and then the traced proof on the Dijkstra page.