Fibonacci Heaps: Degree Bound and Analysis

The Degree Bound Problem

For extract-min to be $O(\log n)$ amortised, we need the consolidation array size (and thus the maximum degree $D(n)$) to be $O(\log n)$. This section proves:

Theorem: In a Fibonacci heap with $n$ nodes, the maximum degree of any node satisfies $D(n) \le \lfloor \log_\phi n \rfloor$ where $\phi = (1+\sqrt{5})/2 \approx 1.618$ is the golden ratio.

Fibonacci Numbers

Define Fibonacci numbers with $F_0 = 0$, $F_1 = 1$:

$F_k = F_{k-1} + F_{k-2} \quad \text{for } k \ge 2$

Sequence: $0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, \ldots$

These satisfy two useful identities:

1. Summation: $F_{k+2} = 1 + \sum_{i=0}^{k} F_i$
2. Golden ratio bound: $F_{k+2} \ge \phi^k$ for all $k \ge 0$ (proved by induction: $\phi^2 = \phi + 1$)

Lemma 1: The Grandchild Ordering

Let $x$ be any node in a Fibonacci heap with degree $k$. Order its children $c_1, c_2, \ldots, c_k$ by the time they were linked as children of $x$ (earliest first). Then:

$c_i.\text{degree} \ge i - 2 \quad \text{for } i = 1, \ldots, k$

Proof:

• When $c_i$ was linked to $x$, both $x$ and $c_i$ had degree at least $i-1$ (since $x$ already had $i-1$ children).
• After linking, $c_i$ could lose at most one child via decrease-key. If it lost a second child, the cascading cut rule would have cut $c_i$ from $x$, and $c_i$ would no longer be a child of $x$.
• Therefore $c_i.\text{degree} \ge (i-1) - 1 = i-2$.

For $i=1$: when $c_1$ was linked, $x$ had degree 0, so $c_1$ had degree 0. $c_1$ could have lost at most one child, so $c_1.\text{degree} \ge 0$, consistent with $i-2 = -1$ (and degree is always $\ge 0$).

Lemma 2: Subtree Size Lower Bound

Define $s_k$ as the minimum number of nodes in any subtree rooted at a node of degree $k$ in a Fibonacci heap. Then:

$s_k \ge F_{k+2}$

Proof by induction:

Base cases:

• $k = 0$: $s_0 \ge 1 = F_2$ (a single root with 0 children)
• $k = 1$: $s_1 \ge 2 = F_3$ (root + one child, which is a degree-0 node)

Inductive step ($k \ge 2$): Consider a node $z$ with degree $k$ and minimal subtree size $s_k$. Order its children by attachment time: $c_1, c_2, \ldots, c_k$.

By Lemma 1, $c_i.\text{degree} \ge i-2$. Since $s_k$ is monotonic (more children cannot give fewer descendants), the subtree rooted at $c_i$ has at least $s_{\max(0, i-2)}$ nodes.

$s_k \ge 1 \text{ (for } z \text{ itself)} + \sum_{i=1}^k s_{\max(0, i-2)}$

For $i=1$: $c_1$ could be degree 0 (initially, or lost its sole child), so at least $s_0$ nodes. For $i=2$: $c_2.\text{degree} \ge 0$, at least $s_0$ nodes. For $i \ge 3$: $c_i.\text{degree} \ge i-2$, at least $s_{i-2}$ nodes.

$s_k \ge 1 + s_0 + s_0 + \sum_{i=3}^k s_{i-2} = 2 + \sum_{i=0}^{k-2} s_i$

By the induction hypothesis $s_i \ge F_{i+2}$ for all $i < k$:

$s_k \ge 2 + \sum_{i=0}^{k-2} F_{i+2} = 2 + \sum_{i=0}^{k-2} F_{i+2}$

Re-index with $j = i+2$: $\sum_{j=2}^k F_j = \sum_{j=0}^k F_j - F_0 - F_1 = \sum_{j=0}^k F_j - 1$.

So $s_k \ge 2 + (\sum_{j=0}^k F_j - 1) = 1 + \sum_{j=0}^k F_j = F_{k+2}$ (using the summation identity).

Proof of the Main Theorem

For any node $x$ in a Fibonacci heap with $k = x.\text{degree}$:

$n \ge \text{size}(x) \ge s_k \ge F_{k+2} \ge \phi^k$

where $n$ is the total number of nodes in the entire heap. Taking logarithms base $\phi$:

$k \le \log_\phi n$

Since $k$ is an integer, $k \le \lfloor \log_\phi n \rfloor$. This holds for every node, so

$D(n) \le \lfloor \log_\phi n \rfloor = O(\log n)$

Concrete Worked Example

For $n = 100$ nodes: $\log_\phi 100 \approx \frac{\ln 100}{\ln 1.618} \approx \frac{4.605}{0.481} \approx 9.57$. So $D(100) \le 9$.

For $n = 10^6$: $\log_\phi 10^6 \approx 28.7$. So $D(10^6) \le 28$.

The consolidation array for extract-min needs only $\lfloor \log_\phi n \rfloor + 1$ entries — very small even for large heaps.

Consequences

1. Consolidation array size: $D(n)+1 = O(\log n)$ — only $O(\log n)$ entries needed.
2. Children promoted during extract-min: at most $D(n)$ children of the old minimum need to be moved to the root list.
3. Extract-min amortised cost: The cancellation $O(r + D(n)) + (D(n)+1 - r) = O(D(n)) = O(\log n)$ depends critically on this degree bound.

The entire efficiency of Fibonacci heaps hinges on this structural guarantee provided by the marking and cascading cut regime.

Summary

Statement	Formula
Lemma 1 (grandchild)	$c_i.\text{degree} \ge i-2$
Lemma 2 (subtree size)	$s_k \ge F_{k+2}$
Fibonacci bound	$F_{k+2} \ge \phi^k$
Degree bound	$k \le \lfloor \log_\phi n \rfloor$
Maximum degree	$D(n) = O(\log n)$
Consolidation array size	$D(n) + 1 = O(\log n)$
Extract-min amortised	$\Theta(\log n)$