Overview

Fibonacci heaps are a sophisticated implementation of mergeable heaps that achieve excellent amortized time bounds by deferring consolidation work. They support INSERT, UNION, and DECREASE-KEY in O(1) amortized time, and EXTRACT-MIN and DELETE in O(lg n) amortized time. These bounds make Fibonacci heaps theoretically optimal for algorithms like Dijkstra's shortest paths and Prim's minimum spanning tree, where DECREASE-KEY is called frequently.

Key Concepts

• Mergeable heap interface: MAKE-HEAP, INSERT, MINIMUM, EXTRACT-MIN, UNION, plus DECREASE-KEY and DELETE.
• Structure: A Fibonacci heap is a collection of min-heap-ordered rooted trees. Roots are linked in a circular, doubly linked root list. A pointer H.min points to the overall minimum node.
• Node attributes: Each node x has x.key, x.degree (number of children), x.p (parent), x.child (one child pointer), x.left/x.right (sibling pointers in circular doubly linked lists), and x.mark (whether x has lost a child since last becoming a child of another node).
• Lazy design philosophy: Operations like INSERT and UNION do minimal work (O(1)), accumulating structural debt. EXTRACT-MIN pays off this debt by consolidating the root list.
• Potential function: Φ(H) = t(H) + 2·m(H), where t(H) is the number of trees in the root list and m(H) is the number of marked nodes. This function drives the amortized analysis.
• Maximum degree bound: D(n) = O(lg n), proved via Fibonacci numbers (the source of the data structure's name).

Algorithms and Techniques

FIB-HEAP-INSERT(H, x)

Initializes x (degree 0, unmarked, no parent/child) and adds it to the root list. Updates H.min if x.key < H.min.key. Increments H.n. Amortized cost: O(1) (potential increases by 1).

FIB-HEAP-UNION(H1, H2)

Concatenates the root lists of H1 and H2, updates the min pointer, and sets H.n = H1.n + H2.n. Amortized cost: O(1) (potential change is 0).

FIB-HEAP-EXTRACT-MIN(H)

The most complex operation:

1. Add all children of the minimum node z to the root list.

2. Remove z from the root list.

3. CONSOLIDATE(H): Repeatedly link roots with the same degree until all roots have distinct degrees. Uses an auxiliary array A[0..D(H.n)] indexed by degree. For each root w, if another root y in A has the same degree, link the one with the larger key under the one with the smaller key, incrementing the winner's degree.

4. Rebuild the root list from array A and find the new minimum.