Chapter 19: Fibonacci Heaps

A Fibonacci heap is a data structure that supports a set of mergeable heap operations. Several of its operations run in constant amortized time, making it well suited for applications that invoke these operations frequently.

Supported Operations

Mergeable Heap Operations

A mergeable heap supports five operations:

1. MAKE-HEAP() — creates and returns a new empty heap
2. INSERT(H, x) — inserts element x (with key already filled in) into heap H
3. MINIMUM(H) — returns a pointer to the element with minimum key
4. EXTRACT-MIN(H) — deletes and returns the element with minimum key
5. UNION(H1, H2) — creates and returns a new heap containing all elements of H1 and H2, destroying both

Fibonacci heaps additionally support:

6. DECREASE-KEY(H, x, k) — assigns element x a new key value k ≤ current key
7. DELETE(H, x) — deletes element x from heap H

Practical Considerations

• Fibonacci heaps are especially desirable when EXTRACT-MIN and DELETE operations are rare relative to other operations (e.g., graph algorithms calling DECREASE-KEY once per edge)
• Used in fast algorithms for minimum spanning trees (Ch. 23) and single-source shortest paths (Ch. 24)
• In practice, constant factors and programming complexity make them less desirable than binary/k-ary heaps for most applications
• SEARCH is not efficiently supported — DECREASE-KEY and DELETE require a pointer to the element

---

Structure of Fibonacci Heaps

A Fibonacci heap is a collection of rooted trees that are min-heap ordered: the key of a node is greater than or equal to the key of its parent.

Node Structure

Each node x contains:

• x.p — pointer to parent
• x.child — pointer to any one of its children
• x.left, x.right — pointers to left and right siblings (children are linked in a circular, doubly linked list called the child list)
• x.degree — number of children in the child list
• x.mark — boolean indicating whether x has lost a child since the last time x was made the child of another node

If node y is an only child, then y.left = y.right = y. Siblings may appear in any order.

Heap Attributes

• H.min — pointer to the root containing the minimum key (the minimum node)
• H.n — total number of nodes in H
• The roots of all trees are linked via left/right pointers into a circular, doubly linked list called the root list
• When H is empty, H.min = NIL

Circular, Doubly Linked Lists

Two key advantages:

1. Insert or remove a node from anywhere in O(1) time
2. Concatenate (splice) two lists into one in O(1) time

Potential Function

For a Fibonacci heap H:

• t(H) = number of trees in the root list
• m(H) = number of marked nodes

Potential:

Φ(H) = t(H) + 2·m(H)

• Initial potential is 0 (application begins with no heaps)
• Potential is always nonnegative, so total amortized cost upper-bounds total actual cost

Maximum Degree

• D(n) = upper bound on the maximum degree of any node in an n-node Fibonacci heap
• With only mergeable-heap operations: D(n) ≤ ⌊lg n⌋
• With DECREASE-KEY and DELETE supported: D(n) = O(lg n)

---

Mergeable-Heap Operations

The key design principle: delay work as long as possible. Insertion is O(1) by simply adding to the root list; the deferred consolidation happens during EXTRACT-MIN.

Creating a New Fibonacci Heap

MAKE-FIB-HEAP()
    allocate and return H with H.n = 0, H.min = NIL

• t(H) = 0, m(H) = 0, so Φ(H) = 0
• Amortized cost: O(1)

Inserting a Node

FIB-HEAP-INSERT(H, x)
1   x.degree = 0
2   x.p = NIL
3   x.child = NIL
4   x.mark = FALSE
5   if H.min == NIL
6       create a root list for H containing just x
7       H.min = x
8   else insert x into H's root list
9       if x.key < H.min.key
10          H.min = x
11  H.n = H.n + 1

• Initializes node attributes, adds x to the root list, updates H.min if needed
• Potential increase: (t(H)+1 + 2·m(H)) − (t(H) + 2·m(H)) = 1
• Amortized cost: O(1)

Finding the Minimum Node

• Simply return H.min
• No potential change
• Amortized cost: O(1)

Uniting Two Fibonacci Heaps

FIB-HEAP-UNION(H1, H2)
1   H = MAKE-FIB-HEAP()
2   H.min = H1.min
3   concatenate the root list of H2 with the root list of H
4   if (H1.min == NIL) or (H2.min ≠ NIL and H2.min.key < H1.min.key)
5       H.min = H2.min
6   H.n = H1.n + H2.n
7   return H

• Concatenates root lists, determines new minimum, sets H.n
• t(H) = t(H1) + t(H2), m(H) = m(H1) + m(H2), so ΔΦ = 0
• Amortized cost: O(1)

Extracting the Minimum Node

FIB-HEAP-EXTRACT-MIN(H)
1   z = H.min
2   if z ≠ NIL
3       for each child x of z
4           add x to the root list of H
5           x.p = NIL
6       remove z from the root list of H
7       if z == z.right
8           H.min = NIL
9       else H.min = z.right
10          CONSOLIDATE(H)
11      H.n = H.n - 1
12  return z

Steps:

1. Make each child of the minimum node a root
2. Remove the minimum node from the root list
3. If the heap is now empty, set H.min = NIL
4. Otherwise, consolidate the root list (link roots of equal degree)
5. Decrement H.n and return the removed node

Consolidation

Repeatedly links roots of equal degree until every root has a distinct degree value.

CONSOLIDATE(H)
1   let A[0 .. D(H.n)] be a new array
2   for i = 0 to D(H.n)
3       A[i] = NIL
4   for each node w in the root list of H
5       x = w
6       d = x.degree
7       while A[d] ≠ NIL
8           y = A[d]              // another node with same degree as x
9           if x.key > y.key
10              exchange x with y
11          FIB-HEAP-LINK(H, y, x)
12          A[d] = NIL
13          d = d + 1
14      A[d] = x
15  H.min = NIL
16  for i = 0 to D(H.n)
17      if A[i] ≠ NIL
18          if H.min == NIL
19              create a root list for H containing just A[i]
20              H.min = A[i]
21          else insert A[i] into H's root list
22              if A[i].key < H.min.key
23                  H.min = A[i]

FIB-HEAP-LINK(H, y, x)
1   remove y from the root list of H
2   make y a child of x, incrementing x.degree
3   y.mark = FALSE

How CONSOLIDATE works:

• Uses auxiliary array A[0 .. D(H.n)] indexed by degree
• Processes each root w: if another root y has the same degree, link the one with the larger key under the smaller, increment degree, repeat
• After processing all roots, rebuild the root list from array A and find the new minimum

Loop invariant for the while loop: at the start of each iteration, d = x.degree.

Amortized Cost of EXTRACT-MIN

• Root list size upon calling CONSOLIDATE: at most D(n) + t(H) − 1
• Total actual work: O(D(n) + t(H))
• Potential before: t(H) + 2·m(H)
• Potential after: at most (D(n) + 1) + 2·m(H)
• Amortized cost:

O(D(n) + t(H)) + (D(n) + 1 + 2·m(H)) − (t(H) + 2·m(H)) = O(D(n)) = O(lg n)

The cost of each link is paid for by the reduction in potential (one fewer root).

---

Decreasing a Key

FIB-HEAP-DECREASE-KEY

FIB-HEAP-DECREASE-KEY(H, x, k)
1   if k > x.key
2       error "new key is greater than current key"
3   x.key = k
4   y = x.p
5   if y ≠ NIL and x.key < y.key
6       CUT(H, x, y)
7       CASCADING-CUT(H, y)
8   if x.key < H.min.key
9       H.min = x

CUT(H, x, y)
1   remove x from the child list of y, decrementing y.degree
2   add x to the root list of H
3   x.p = NIL
4   x.mark = FALSE

CASCADING-CUT(H, y)
1   z = y.p
2   if z ≠ NIL
3       if y.mark == FALSE
4           y.mark = TRUE
5       else CUT(H, y, z)
6           CASCADING-CUT(H, z)

How It Works

1. Assign the new key k to x
2. If x is a root or min-heap order is not violated, just update H.min if needed
3. Otherwise, cut x from its parent y (make x a root, clear its mark)
4. Perform cascading cuts up the tree:
   • If parent y is a root → stop
   • If y is unmarked → mark it (first child lost) and stop
   • If y is marked → cut y from its parent, make y a root, unmark it, recurse on y's parent

Mark Bit Semantics

The mark attribute records history:

1. x was a root
2. x was linked to (made child of) another node
3. One child of x was removed by a cut

When the second child is lost, x is cut from its parent (cascading cut). The mark is cleared whenever a node becomes a root or is linked as a child.

Amortized Cost of DECREASE-KEY

Let c = number of calls to CASCADING-CUT:

• Actual cost: O(c)
• After the operation: t(H) + c trees, at most m(H) − c + 2 marked nodes
• Potential change: at most (t(H) + c + 2(m(H) − c + 2)) − (t(H) + 2·m(H)) = 4 − c
• Amortized cost: O(c) + 4 − c = O(1)

The factor of 2 on marked nodes in the potential function is key: when a marked node is cut, clearing its mark reduces potential by 2 — one unit pays for the cut, the other compensates for the new root.

---

Deleting a Node

FIB-HEAP-DELETE(H, x)
1   FIB-HEAP-DECREASE-KEY(H, x, -∞)
2   FIB-HEAP-EXTRACT-MIN(H)

• Decrease x's key to −∞, making it the minimum
• Extract the minimum (which is now x)
• Amortized cost: O(1) + O(D(n)) = O(D(n)) = O(lg n)

---

Bounding the Maximum Degree

The goal: show that D(n) = O(lg n), which validates the amortized bounds for EXTRACT-MIN and DELETE.

Key Idea

For each node x, define size(x) = number of nodes in the subtree rooted at x (including x). We show that size(x) is exponential in x.degree, which bounds the maximum degree logarithmically.

Lemma 19.1

Let x be any node with x.degree = k, and let y₁, y₂, ..., yₖ be the children of x in the order they were linked to x (earliest to latest). Then:

• y₁.degree ≥ 0
• yᵢ.degree ≥ i − 2 for i = 2, 3, ..., k

Proof sketch: When yᵢ was linked to x, x already had children y₁ through yᵢ₋₁, so x.degree ≥ i − 1. Since linking only occurs when degrees match, yᵢ.degree ≥ i − 1 at that time. Since then, yᵢ has lost at most one child (it would have been cut if it lost two), so yᵢ.degree ≥ i − 2.

Fibonacci Numbers Connection

Recall the Fibonacci numbers: F₀ = 0, F₁ = 1, Fₖ = Fₖ₋₁ + Fₖ₋₂ for k ≥ 2.

Lemma 19.2: For all k ≥ 0:

F_{k+2} = 1 + Σᵢ₌₀ᵏ Fᵢ

Lemma 19.3: For all k ≥ 0:

F_{k+2} ≥ φᵏ

where φ = (1 + √5)/2 ≈ 1.61803 is the golden ratio.

Lemma 19.4

Let x be any node in a Fibonacci heap with x.degree = k. Then:

size(x) ≥ F_{k+2} ≥ φᵏ

Proof sketch:

• Let sₖ = minimum possible size of any node of degree k
• s₀ = 1, s₁ = 2
• For the children y₁, ..., yₖ of a degree-k node: size(x) ≥ sₖ ≥ 2 + Σᵢ₌₂ᵏ sᵢ₋₂
• By induction using Lemma 19.1 and Lemma 19.2: sₖ ≥ F_{k+2} ≥ φᵏ

Corollary 19.5

The maximum degree D(n) of any node in an n-node Fibonacci heap is O(lg n).

Proof: From Lemma 19.4, n ≥ size(x) ≥ φᵏ. Taking base-φ logarithms: k ≤ log_φ(n). Since k is an integer, k ≤ ⌊log_φ(n)⌋. Thus D(n) = O(lg n).

This is why the data structure is called a Fibonacci heap — the Fibonacci numbers arise naturally in bounding the maximum degree.