Why Fibonacci Numbers Appear in Fibonacci Heaps

The reason Fibonacci numbers appear in the analysis of Fibonacci heaps is due to the structure of the trees within the heap.

Specifically, the maximum degree $D(n)$ of any node in a Fibonacci heap with $n$ nodes is $O(\log n)$. Specifically:

$D(n)\le {\log }_{\varphi }n\approx 1.44{\log }_{2}n$

Where $\varphi =\frac{1+\sqrt{5}}{2}\approx 1.618$ is the golden ratio.

This bound follows from an important invariant maintained by Fibonacci heaps:

A node of degree $d$ must have at least $F_{d+2}$ descendants, where $F_k$ is the $k$-th Fibonacci number.

As a result, to support $n$ nodes, no node can have degree above $O(\log n)$. Therefore the consolidate operation uses an auxiliary array $A$ of size $\lfloor {\log }_{2}n\rfloor +1$, sufficient to index all possible degrees.

The Relationship Between Size & Degree

For a Fibonacci Heap, for any node $x$, define:

• size(x): The total number of nodes in the subtree rooted at node $x$ (including $x$)
• degree(x): The number of children of node $x$
• $F_k$: The $k$-th Fibonacci number

Using the identity:

${\sum }_{i=0}^k{F}_i=F_{k+2}-1$

We will prove, by induction, that:

$$\text{size}(x)\ge F_{\text{degree}(x)+2}$$

To establish that the invariant — “a node of degree $d$ has at least $F_{d+2}$ descendants”, hold true.

Base Case

If the subtree rooted at $x$ has no children (i.e., $\text{degree}(x)=0$), then it consists of only one node. Hence:

• $\text{size}(x)=1$ and,
• $F_{\text{degree}(x)+2}=F_2=1$

Therefore $\text{size}(x)\ge F_2$ and so the inequality holds in the base case.

Inductive Step

Let $x$ have $d$ children ($\text{degree}(x)=d$) and let its children be $c_1,c_2,\dots ,c_d$, in the order they were added.

Then, the size of the subtree rooted at $x$ is:

$\text{size}(x)=1+\text{size}(c_1)+\text{size}(c_2)+\cdots +\text{size}(c_d)=1+{\sum }_{i=1}^d\text{size}(c_i)$

Then by the inductive hypothesis, each child satisfies:

$$\text{size}(c_i)\ge F_{\text{degree}(c_i)+2}$$

Therefore

$\text{size}(x)\ge 1+{\sum }_{i=1}^d{F}_{\text{degree}(c_i)+2}$

To derive a meaningful lower bound, we must now find a lower bound on each $\text{degree}(c_i)$.

Bounding The Degree & Size

Each child $c_i$ became a child of $x$ during a consolidate operation, which only merges trees of equal degree.

• Suppose $c_i$ was the $i$-th child added, i.e. $x$ already had $i-1$ children
• Therefore, just before merging with $c_i$, $\text{degree}(x)=i-1$.
• At the time of merging, $\text{degree}(x)=\text{degree}(c_i)=i-1$

However, due to decrease-key, $c_i$ might have lost at most one child (any more would cause it to be cut and moved to the root list). So we conservatively say:

$\text{degree}(c_i)\ge i-2$

This bound can be substituted back to bound the size of $x$

$$\begin{array}{rl}\text{size}(x)& \ge 1+\sum _{i=1}^d{F}_{\text{degree}(c_i)+2}\\ & \ge 1+\sum _{i=1}^d{F}_{(i-2)+2}\\ & \ge 1+0+\sum _{i=1}^d{F}_i\\ & \ge 1+F_0+\sum _{i=1}^d{F}_i\\ & \ge 1+\sum _{i=0}^d{F}_i\end{array}$$

We now use the identity:

${\sum }_{i=0}^k{F}_i=F_{k+2}-1$

So:

$\text{size}(x)\ge 1+(F_{d+2}-1)\ge F_{d+2}$

Thus, the subtree rooted at any node $x$ with degree $d$ contains at least $F_{d+2}$ nodes.

Maximum Degree And Efficiency

From above, for any node in a Fibonacci heap with degree $d$,

$\text{size}(x)\ge F_{d+2}$

We also know that Fibonacci numbers grow exponentially with the golden ratio $\phi =\frac{1+\sqrt{5}}{2}$:

$F_{d+2}\ge {\phi }^d$

Now, suppose the Fibonacci heap has $n$ nodes total. Since $\text{size}(x)\le n$, we get:

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

Taking logs:

$d\le {\log }_{\phi }n$

This proves the maximum degree $D(n)$ of any node in a Fibonacci heap is bounded by ${\log }_{\phi }n$. This $O(\log n)$ bound directly ensures efficient extract-min and consolidate operations by limiting the number of distinct degrees in the root list.