Editing Fibonacci heap (section)

==Proof of degree bounds==
The amortized performance of a Fibonacci heap depends on the degree (number of children) of any tree root being <math>O(\log n)</math>, where <math>n</math> is the size of the heap. Here we show that the size of the (sub)tree rooted at any node <math>x</math> of degree <math>d</math> in the heap must have size at least <math>F_{d+2}</math>, where <math>F_i</math> is the <math>i</math>th [[Fibonacci number]].  The degree bound follows from this and the fact (easily proved by induction) that <math>F_{d+2} \ge \varphi^d</math> for all integers <math>d\ge 0</math>, where <math>\varphi = (1+\sqrt 5)/2 \approx 1.618</math> is the [[golden ratio]].  We then have <math>n \ge F_{d+2} \ge \varphi^d</math>, and taking the log to base <math>\varphi</math> of both sides gives <math>d\le \log_{\varphi} n</math> as required.

Let <math>x</math> be an arbitrary node in a Fibonacci heap, not necessarily a root. Define <math>\mathrm{size}(x)</math> to be the size of the tree rooted at <math>x</math> (the number of descendants of <math>x</math>, including <math>x</math> itself). We prove by induction on the height of <math>x</math> (the length of the longest path from <math>x</math> to a descendant leaf) that <math>\mathrm{size}(x) \ge F_{d+2}</math>, where <math>d</math> is the degree of <math>x</math>.

'''Base case:''' If <math>x</math> has height <math>0</math>, then <math>d=0</math>, and <math>\mathrm{size}(x) = 1 \ge F_2</math>.

'''Inductive case:'''  Suppose <math>x</math> has positive height and degree <math>d>0</math>.  Let <math>y_1, y_2 \dots y_d</math> be the children of <math>x</math>, indexed in order of the times they were most recently made children of <math>x</math> (<math>y_1</math> being the earliest and <math>y_d</math> the latest), and let <math>c_1, c_2 \dots c_d</math> be their respective degrees.

We claim that <math>c_i \ge i-2</math> for each <math>i</math>. Just before <math>y_i</math> was made a child of <math>x</math>, <math>y_1 \dots y_{i-1}</math> were already children of <math>x</math>, and so <math>x</math> must have had degree at least <math>i-1</math> at that time. Since trees are combined only when the degrees of their roots are equal, it must have been the case that <math>y_i</math> also had degree at least <math>i-1</math> at the time when it became a child of <math>x</math>. From that time to the present, <math>y_i</math> could have only lost at most one child (as guaranteed by the marking process), and so its current degree <math>c_i</math> is at least <math>i-2</math>. This proves the claim.

Since the heights of all the <math>y_i</math> are strictly less than that of <math>x</math>, we can apply the inductive hypothesis to them to get<math display="block">\mathrm{size}(y_i) \ge F_{c_i+2} \ge F_{(i-2)+2} = F_i.</math>The nodes <math>x</math> and <math>y_1</math> each contribute at least 1 to <math>\mathrm{size}(x)</math>, and so we have<math display="block">\begin{align}
\mathrm{size}(x)
&\ge 2 + \sum_{i=2}^d \mathrm{size}(y_i) \\
&\ge 2 + \sum_{i=2}^d F_i \\
&= 1 + \sum_{i=0}^d F_i \\
&= F_{d+2}
\end{align}</math>where the last step is an identity for Fibonacci numbers. This gives the desired lower bound on <math>\mathrm{size}(x)</math>.