Fibonacci Heaps

Chapter 1: Structure

Forget everything you know about binary heaps. A binary heap is a single, perfectly balanced tree stored in an array. A Fibonacci heap is nothing like that. It is a collection of trees — a messy forest where trees can have any shape, any size, and there can be any number of them.

The Forest of Trees

A Fibonacci heap is a collection of min-heap-ordered trees. "Min-heap-ordered" means that in each tree, every node's key is less than or equal to the keys of its children. But unlike a binary heap, these trees are not necessarily binary — a node can have 0, 1, 2, 3, or more children.

All the roots of these trees are linked together in a circular doubly-linked list called the root list. The heap maintains a single pointer called min that points to the root with the smallest key in the entire heap.

Node Structure

Each node in a Fibonacci heap stores more information than a binary heap node:

python
class FibNode:
    def __init__(self, key):
        self.key = key       # the priority value
        self.degree = 0     # number of children
        self.mark = False    # has this node lost a child since
                              # it became a child of its current parent?
        self.parent = None   # pointer to parent
        self.child = None    # pointer to one child (any child)
        self.left = self      # left sibling (circular)
        self.right = self     # right sibling (circular)

The degree field counts how many children a node has. The mark field is the secret weapon — it tracks whether a node has lost a child since it was last made a child of another node. This mark drives the cascading-cut mechanism that keeps the trees from getting too tall. We will cover it in Chapter 4.

The left and right pointers form circular doubly-linked lists at every level. A node's children are linked in a circular list, and the roots are linked in a circular list. The child pointer points to any one of the node's children — you can then traverse the child's left/right pointers to visit all siblings.

The Heap Object

python
class FibHeap:
    def __init__(self):
        self.min = None   # pointer to the minimum root
        self.n = 0        # total number of nodes

That is it. The heap object is just two fields: a pointer to the minimum and a count of total nodes. The entire structure is held together by pointer links between nodes.

A Visual Example

Suppose we have a Fibonacci heap with 14 nodes. It might look like this: three trees in the root list with min pointing to the smallest root. One tree has degree 3 (three children), another has degree 1, and the third is a single node with degree 0.

Key Properties

Let us be precise about what a Fibonacci heap guarantees:

1. Min-heap order within each tree. For every non-root node x, x.key ≥ x.parent.key. The minimum of the entire heap is always one of the roots.

2. Roots linked in a circular doubly-linked list. We can splice, insert, and remove from this list in O(1).

3. Children linked in circular doubly-linked lists. Same O(1) splicing for child lists.

4. The min pointer always accurate. H.min points to the root with the smallest key.

What is NOT guaranteed: the number of trees, the shape of trees, the degree of any node, or any balance condition. The structure is deliberately loose — that looseness is what makes insert, union, and decrease-key O(1).

Comparing with Binary Heaps

Chapter 2: Mergeable Heap Operations

The first three operations on a Fibonacci heap — INSERT, MINIMUM, and UNION — are almost comically simple. They do the absolute minimum amount of work and defer everything else. This is the essence of the Fibonacci heap philosophy: be lazy now, pay later.

INSERT

FIB-HEAP-INSERT(H, x): Create a new node x as a single-node tree. Add it to the root list. If x.key < H.min.key, update H.min to x. Increment H.n.

python
def insert(self, key):
    node = FibNode(key)
    if self.min is None:
        # empty heap — node becomes the only root
        self.min = node
    else:
        # splice node into root list next to min
        self._add_to_root_list(node)
        if node.key < self.min.key:
            self.min = node
    self.n += 1
    return node  # return handle for decrease-key

That is O(1). No sifting, no rebalancing, no comparisons except the single comparison with the current minimum. The new node just gets tossed onto the root list.

Notice that insert returns the node. This is important — to call decrease-key later, the caller must have a direct pointer to the node. Without this handle, you would need O(n) to find the node first, defeating the purpose of O(1) decrease-key.

MINIMUM

FIB-HEAP-MINIMUM(H): Return H.min.key.

python
def minimum(self):
    return self.min.key  # O(1) — just follow the pointer

Nothing to explain. The pointer is always maintained. O(1).

UNION

FIB-HEAP-UNION(H1, H2): Concatenate the root lists of H1 and H2. Update min to whichever is smaller. Set n = H1.n + H2.n.

python
def union(h1, h2):
    h = FibHeap()
    h.min = h1.min
    # concatenate root lists — splice two circular lists
    if h1.min and h2.min:
        h1_right = h1.min.right
        h2_left = h2.min.left
        h1.min.right = h2.min
        h2.min.left = h1.min
        h1_right.left = h2_left   # was h2_left
        h2_left.right = h1_right
    if h2.min and (h1.min is None or h2.min.key < h1.min.key):
        h.min = h2.min
    h.n = h1.n + h2.n
    return h

This is O(1). Four pointer rewires to splice two circular lists. One comparison to update min. Done.

Circular List Splicing

The circular list splice is the fundamental operation. Let us trace through it carefully, because it appears everywhere in Fibonacci heap code.

Suppose list A has roots [a1 ↔ a2 ↔ a3] (circular, so a3.right = a1) and list B has roots [b1 ↔ b2]. To splice B into A after a1:

Four pointer changes. Constant time regardless of list sizes. This is why everything that only involves list manipulation is O(1).

Hand Calculation: 5 Inserts

Let us trace 5 inserts into an empty Fibonacci heap: INSERT(7), INSERT(3), INSERT(11), INSERT(1), INSERT(9).

After INSERT(7): Root list = [7]. min = 7. n = 1.

After INSERT(3): Root list = [7, 3]. min = 3 (3 < 7). n = 2.

After INSERT(11): Root list = [7, 3, 11]. min = 3 (3 < 11). n = 3.

After INSERT(1): Root list = [7, 3, 11, 1]. min = 1 (1 < 3). n = 4.

After INSERT(9): Root list = [7, 3, 11, 1, 9]. min = 1 (1 < 9). n = 5.

Five inserts produced five single-node trees in the root list. No tree has any children. The minimum is correctly 1. Total work: 5 comparisons. That is it.

Chapter 3: EXTRACT-MIN

Here is where the Fibonacci heap pays for its laziness. EXTRACT-MIN is the one operation that actually does significant work — it removes the minimum, promotes its children to roots, and then consolidates the root list so that no two roots have the same degree.

The Algorithm

FIB-HEAP-EXTRACT-MIN(H):

Step 1. Take the min node z = H.min. Add all of z's children to the root list (remove their parent pointers). This takes O(degree(z)) time.

Step 2. Remove z from the root list.

Step 3. If z was the only node (z.right == z and z had no children), set H.min = NIL.

Step 4. Otherwise, set H.min = z.right (temporarily — this might not be the actual minimum). Then call CONSOLIDATE.

Step 5. Decrement H.n. Return z.

CONSOLIDATE — The Heart of Extract-Min

CONSOLIDATE is where the real work happens. The goal: merge trees in the root list until no two roots have the same degree. This is like radix bucketing — we use an array A[0 .. D(n)] indexed by degree.

python
def _consolidate(self):
    # max possible degree: floor(log_phi(n))
    max_degree = int(math.log(self.n, (1+math.sqrt(5))/2)) + 1
    A = [None] * (max_degree + 1)

    # collect all roots into a list (can't modify while iterating circular list)
    roots = []
    x = self.min
    if x:
        curr = x
        while True:
            roots.append(curr)
            curr = curr.right
            if curr == x: break

    for w in roots:
        x = w
        d = x.degree
        while A[d] is not None:
            y = A[d]          # another root with same degree
            if x.key > y.key:
                x, y = y, x  # x is the smaller one
            self._link(y, x)   # make y a child of x
            A[d] = None
            d += 1             # x now has one more child
        A[d] = x

    # rebuild root list from A
    self.min = None
    for node in A:
        if node is not None:
            node.left = node.right = node
            if self.min is None:
                self.min = node
            else:
                self._add_to_root_list(node)
                if node.key < self.min.key:
                    self.min = node

The LINK Operation

FIB-HEAP-LINK(y, x): Make y a child of x. Remove y from the root list. Add y to x's child list. Increment x.degree. Unmark y (y.mark = False).

python
def _link(self, y, x):
    # remove y from root list
    y.left.right = y.right
    y.right.left = y.left
    # make y a child of x
    y.parent = x
    if x.child is None:
        x.child = y
        y.left = y.right = y
    else:
        # splice y into x's child list
        y.right = x.child.right
        y.left = x.child
        x.child.right.left = y
        x.child.right = y
    x.degree += 1
    y.mark = False

Worked Example: Extract-Min with Consolidation

Suppose we have a Fibonacci heap with 7 nodes all in the root list (after 7 inserts, no extractions): keys [3, 7, 11, 1, 9, 5, 13]. H.min points to 1.

Step 1: Remove 1 from root list. Node 1 has no children (it was a single-node tree). Root list is now [3, 7, 11, 9, 5, 13] — six degree-0 trees.

Step 2: Consolidate. We walk through the roots. Array A is indexed by degree.

We started with 6 single-node trees and ended with 2 trees after consolidation. The degree array ensured no two roots share a degree.

Amortized Cost of Extract-Min

The actual cost of extract-min is O(D(n) + t) where D(n) is the maximum degree of any node (we will prove D(n) = O(log n) in Chapter 7) and t is the number of trees in the root list before consolidation. After consolidation, at most D(n) + 1 trees remain (one per degree). The amortized cost is O(D(n)) = O(log n) — the potential drop from reducing t trees to at most D(n) + 1 trees pays for the extra work.

Chapter 4: DECREASE-KEY

This is the star of the show. DECREASE-KEY is the operation that makes Fibonacci heaps worth the complexity — O(1) amortized time to lower a node's key. It achieves this through a mechanism called cascading cuts.

The Basic Idea

When we decrease a node's key, the min-heap property might be violated — the node might now be smaller than its parent. In a binary heap, we would "bubble up" the node, which costs O(log n) in the worst case. A Fibonacci heap does something more aggressive: it cuts the node from its parent and moves it to the root list. This is O(1).

But there is a catch. If we keep cutting children from the same parent, that parent's tree becomes too sparse — it has a high degree but few descendants. This would break the degree bound we need for extract-min to be efficient. The solution: the mark mechanism and cascading cuts.

The Mark Mechanism

Every non-root node has a boolean mark field. The rules are simple:

1. When a node is first made a child of another node (during consolidation or linking), it is unmarked.

2. When a node loses its first child (due to a cut), it gets marked. This is a warning: "I have already lost one child."

3. When a marked node loses a second child, we cut it from its parent too (and unmark it). This is the cascading cut.

The Algorithm

python
def decrease_key(self, x, new_key):
    assert new_key <= x.key, "new key must be smaller"
    x.key = new_key
    y = x.parent
    if y is not None and x.key < y.key:
        self._cut(x, y)
        self._cascading_cut(y)
    if x.key < self.min.key:
        self.min = x

def _cut(self, x, y):
    # remove x from y's child list
    if x.right == x:
        y.child = None
    else:
        x.left.right = x.right
        x.right.left = x.left
        if y.child == x:
            y.child = x.right
    y.degree -= 1
    # add x to root list
    self._add_to_root_list(x)
    x.parent = None
    x.mark = False

def _cascading_cut(self, y):
    z = y.parent
    if z is not None:     # y is not a root
        if not y.mark:
            y.mark = True    # first child lost — just mark
        else:
            self._cut(y, z) # second child lost — cut!
            self._cascading_cut(z) # check grandparent

Worked Example: Decrease-Key with Cascading Cut

Consider a tree rooted at 3 with the following structure (marks shown as *):

Node 9 is marked (it lost a child previously). Now we call DECREASE-KEY(18, 2).

Step 1: Set 18.key = 2. Parent is 7. 2 < 7, so we need to cut.

Step 2: CUT(18, 7). Remove 18 from 7's child list. Add 18 to root list. Unmark 18 (it was not marked anyway). 7's degree drops from 1 to 0.

Step 3: CASCADING-CUT(7). 7's parent is 3. Is 7 marked? No. So just mark 7. Done.

Step 4: 2 < 3 (current min), so update H.min = 2.

Now suppose we call DECREASE-KEY(11, 1).

Step 1: Set 11.key = 1. Parent is 9. 1 < 9, so cut.

Step 2: CUT(11, 9). Remove 11 from 9's child list. Add 11 to root list. 9's degree drops to 0.

Step 3: CASCADING-CUT(9). 9's parent is 3. Is 9 marked? YES. So cut 9 from 3!

Step 3a: CUT(9, 3). Remove 9 from 3's child list. Add 9 to root list. Unmark 9. 3's degree drops.

Step 3b: CASCADING-CUT(3). 3 is a root (no parent). Stop.

The cascading cut propagated up one level because 9 was marked. If 3 had also been marked, the cascade would have continued further. In the worst case, a cascade can climb all the way to the root — but the amortized cost is still O(1) because each cascading cut decreases the number of marked nodes.

Why Cascading Cuts are Necessary

Without cascading cuts, a node of degree k could have had arbitrarily many children cut away. It would look like it should have a big subtree (high degree) but actually have very few descendants. This breaks the degree bound D(n) = O(log n) that we need for extract-min to be efficient.

The cascading cut ensures that no non-root node can lose more than one child. If a node has degree k, it still has at least k-1 of its original children (one may have been cut, leaving it marked). This keeps the subtree sizes large enough to maintain the logarithmic degree bound.

Chapter 5: DELETE

DELETE is the simplest operation to describe, because it is just a combination of the two operations we already know.

The Algorithm

FIB-HEAP-DELETE(H, x): Decrease x's key to negative infinity, then extract the minimum. Since x now has the smallest possible key, it will be the minimum that gets extracted.

python
def delete(self, x):
    self.decrease_key(x, float('-inf'))
    self.extract_min()

Two lines. That is the entire implementation.

Why This Works

Step 1: decrease_key(x, -infinity). This cuts x from its parent (if it has one) and adds it to the root list. The cascading cut runs on x's parent. Since -infinity is smaller than any other key, H.min is updated to point to x.

Step 2: extract_min(). Since x is now the minimum, extract_min removes x, promotes its children to roots, and consolidates. All in O(log n) amortized.

Amortized Cost

DECREASE-KEY is O(1) amortized. EXTRACT-MIN is O(log n) amortized. Therefore DELETE is O(log n) amortized. This matches the binary heap's O(log n) delete (which is also typically implemented as decrease-key followed by extract).

Worked Example

Consider a Fibonacci heap where we want to delete node 15:

Step 1: decrease_key(15, -∞). 15 is marked (shown as *). Its key becomes -∞. -∞ < 8 (parent), so CUT(15, 8). Add 15 (now -∞) to root list. 8 was not marked, so mark 8. H.min = -∞ node.

Step 2: extract_min(). Remove -∞ node. Its children (17, 20) become roots. Consolidate the root list [3, 8, 17, 20]. The result depends on degrees during consolidation, but the -∞ node is gone and the heap is valid.

All Operations Summary

Notice that the worst-case for extract-min and decrease-key is O(n) — if all n nodes are in the root list, consolidation touches all of them. The amortized bounds are what matter: over a sequence of operations, the average cost per operation matches the amortized column.

Chapter 6: Amortized Analysis

We have claimed that insert is O(1) amortized, extract-min is O(log n) amortized, and decrease-key is O(1) amortized. Now we prove it. The tool is the potential method.

The Potential Function

Define the potential of a Fibonacci heap H as:

where t(H) is the number of trees in the root list and m(H) is the number of marked nodes in the entire heap.

The amortized cost of an operation is: amortized = actual + ΔΦ = actual + (Φ_after - Φ_before).

If an operation increases the potential, it "stores credit" for future operations. If it decreases the potential, it "spends saved credit." The key insight: operations that seem expensive (long cascading cuts) actually decrease the potential by so much that their amortized cost is cheap.

INSERT Analysis

Actual cost: O(1) — add a node to the root list, maybe update min.

Potential change: We add one tree to the root list, and the new node is not marked. So ΔΦ = +1 + 2(0) = +1.

Amortized cost: O(1) + 1 = O(1).

EXTRACT-MIN Analysis

Actual cost: O(D(n) + t) where D(n) is the max degree and t is the number of trees before consolidation. We add D(n) children to the root list and process t + D(n) trees during consolidation.

Potential change: Before: t trees. After consolidation: at most D(n) + 1 trees (one per degree). No nodes get marked or unmarked in this process. So ΔΦ = (D(n) + 1) - t.

Amortized cost: O(D(n) + t) + (D(n) + 1 - t) = O(D(n) + t) + D(n) + 1 - t = O(D(n)) because the +t actual and -t potential cancel. Since D(n) = O(log n), the amortized cost is O(log n).

DECREASE-KEY Analysis

Suppose decrease-key triggers c cascading cuts (including the initial cut of the node itself).

Actual cost: O(c) — one cut operation per cascade level.

Potential change:

Trees: we add c new trees to the root list (each cut creates a new root). Δt = +c.

Marks: the initial cut unmarks the node (but it might not have been marked). Each cascading cut unmarks one marked node. The final step either marks one previously unmarked node or does nothing (if we reached a root). In the worst case, c-1 marked nodes get cut and unmarked, and 1 node gets newly marked. Δm ≤ -(c - 1) + 1 = -(c - 2).

ΔΦ = c + 2(-(c - 2)) = c - 2c + 4 = -c + 4.

Amortized cost: O(c) + (-c + 4) = O(1). The c actual work is exactly cancelled by the c potential drop.

The Big Interactive Simulation

Summary Table

Chapter 7: The Maximum Degree Bound

The entire amortized analysis depends on D(n) = O(log n). But why is this true? Why can't a root node accumulate an enormous number of children?

The Key Lemma

Let x be any node in a Fibonacci heap, and let x have degree k. Let y₁, y₂, ..., y_k be the children of x in the order they were linked (oldest first). Then:

Why? When y_i was linked to x, x already had children y₁, ..., y_i-1, so x had degree at least i-1. Since CONSOLIDATE only links trees of equal degree, y_i also had degree at least i-1 at the time it was linked. Since then, y_i could have lost at most one child (if it lost two, cascading cut would have removed it). So y_i.degree ≥ (i-1) - 1 = i - 2.

Fibonacci Numbers Appear

Let size(x) denote the number of nodes in the subtree rooted at x (including x). We want to show that size(x) grows exponentially with degree(x).

Let s_k be the minimum possible size of a subtree rooted at a node of degree k. From the lemma above, a degree-k node has children with degrees at least 0, 0, 1, 2, 3, ..., k-2. So:

The 2 accounts for the node itself and the first child (degree ≥ 0, so at least 1 node). The sum accounts for children 2 through k.

Computing the first few values:

The sequence 1, 2, 3, 5, 8, 13, ... These are the Fibonacci numbers! Specifically, s_k = F_k+2 where F is the standard Fibonacci sequence (F₀ = 0, F₁ = 1, F₂ = 1, F₃ = 2, F₄ = 3, F₅ = 5, ...). One can prove by induction that s_k ≥ F_k+2.

The Golden Ratio Connection

The Fibonacci numbers satisfy F_k ≥ φ^k-2 where φ = (1 + √5) / 2 ≈ 1.618 is the golden ratio.

Since size(x) ≥ s_k ≥ F_k+2 ≥ φ^k, and size(x) ≤ n, we get:

Therefore the maximum degree D(n) ≤ ⌊log_φ(n)⌋. For n = 1,000,000: D(n) ≤ log_φ(1,000,000) ≈ 1.4404 × 20 ≈ 29. Compare with log₂(1,000,000) ≈ 20 for a binary heap. The Fibonacci heap's max degree is about 44% higher, but still O(log n).

The Minimum Tree Sizes

Notice that s_k = F_k+2 exactly. The Fibonacci numbers are not just a lower bound — they are the exact minimum. You can construct trees that achieve this minimum: each child has lost exactly one child, creating the sparsest possible tree.

Chapter 8: Fibonacci Heaps in Practice

The theoretical superiority of Fibonacci heaps is undeniable — O(1) decrease-key is unbeatable asymptotically. But asymptotic notation hides constant factors, and those constants matter enormously in practice.

Why Fibonacci Heaps Often Lose

1. Pointer overhead. Each node in a Fibonacci heap stores 5 pointers (parent, child, left, right) plus degree and mark. In a binary heap, each node is just a key in an array — no pointers at all. For 64-bit keys, a Fibonacci heap node is about 56 bytes (7 fields × 8 bytes). A binary heap element is 8 bytes. That is 7x memory overhead.

2. Cache behavior. A binary heap is stored in a contiguous array. Traversing it hits the CPU cache beautifully — adjacent elements are in the same cache line. A Fibonacci heap scatters nodes across the heap (memory allocator sense), with pointer chasing at every step. Each pointer dereference is a potential cache miss (100+ cycles on modern hardware).

3. Allocation cost. Each insert into a Fibonacci heap allocates a new node on the heap. Each extract-min potentially frees a node. Dynamic allocation is expensive — a single malloc/free pair can cost 50-100 nanoseconds. Binary heap insert is just an array write.

4. Constant factors in consolidation. The consolidation loop involves many pointer rewires per merge. Each merge in a binary heap is a single compare-and-swap on array elements.

Practical Alternatives

Pairing heaps. Invented by Fredman, Sedgewick, Sleator, and Tarjan (1986). Much simpler than Fibonacci heaps — no mark field, no cascading cuts. The analysis is more complex (the exact amortized bound for decrease-key is still an open problem!), but empirically they perform nearly as well as Fibonacci heaps and are much faster in practice due to simpler code and fewer pointer operations.

Brodal queues. Achieve O(1) worst-case (not amortized) decrease-key. This is the theoretical optimum. But the implementation is so complex that no one uses them in practice. They are mainly of theoretical interest.

d-ary heaps. A generalization of binary heaps where each node has d children instead of 2. With d = 4 or d = 8, decrease-key costs O(log_d n) which is smaller than O(log₂ n), and the cache behavior is excellent because the wider tree has fewer levels. For Dijkstra, a 4-ary heap often beats all other implementations for sparse to moderate graphs.

Rank-pairing heaps. A recent (2009) data structure that achieves the same amortized bounds as Fibonacci heaps but with simpler code and fewer structural constraints. They use ranks instead of degrees and a simplified cascade mechanism.

* = amortized. ? = exact bound still open.

When to Actually Use a Fibonacci Heap

Use a Fibonacci heap (or pairing heap) when ALL of the following hold:

1. You need decrease-key (not just insert + extract-min).

2. The number of decrease-key operations greatly exceeds the number of extract-min operations (high E/V ratio in Dijkstra).

3. The graph is large enough that the asymptotic advantage overcomes the constant-factor overhead.

4. You are willing to accept the implementation complexity (or you use a library).

Chapter 9: Interview Arsenal & Connections

The Five-Dimensional Cheat Sheet

Here is everything you need to know about Fibonacci heaps, organized by interview dimension:

CONCEPT: A Fibonacci heap is a collection of min-heap-ordered trees in a circular root list. It achieves O(1) amortized insert, union, and decrease-key by deferring structural cleanup to extract-min. The mark field and cascading-cut mechanism ensure that no node loses more than one child, maintaining the D(n) = O(log n) degree bound.

DESIGN: Use Fibonacci heaps when your algorithm does many more decrease-key operations than extract-min operations (dense graph algorithms). The lazy consolidation strategy trades individual operation efficiency for aggregate amortized efficiency. In practice, pairing heaps or d-ary heaps are almost always better choices.

CODE: You will not implement a Fibonacci heap in an interview. But you should be able to explain: (1) insert = add to root list, (2) extract-min = remove min + consolidate, (3) decrease-key = cut + cascade, (4) the potential function Φ = t + 2m.

DEBUG: Common Fibonacci heap bugs: forgetting to update min pointer after consolidation, not handling the circular list correctly during splice/remove, forgetting to unmark nodes when they become roots, incorrectly updating degree during link/cut.

FRONTIER: Strict Fibonacci heaps (Brodal et al., 2012) achieve all the Fibonacci heap bounds in worst-case time, not just amortized. Hollow heaps (2015) simplify the decrease-key mechanism while maintaining the same bounds. The exact amortized complexity of pairing heaps' decrease-key remains an open problem in theoretical CS.

Complete Heap Comparison

* = amortized

Graph Algorithm Impact

Key Takeaways for Interviews

Related Lessons

Chapter 6: Heapsort & Priority Queues — Binary heaps from the ground up. The foundation for understanding why Fibonacci heaps improve on them.

Chapter 24: Single-Source Shortest Paths — Dijkstra's algorithm, the primary client of Fibonacci heaps.

Chapter 23: Minimum Spanning Trees — Prim's algorithm, the other major client.

Chapter 17: Amortized Analysis — The potential method used to analyze Fibonacci heap operations.