Fibonacci Heap - Proof of Degree Bounds

Proof of Degree Bounds

The amortized performance of a Fibonacci heap depends on the degree (number of children) of any tree root being O(log n), where n is the size of the heap. Here we show that the size of the (sub)tree rooted at any node x of degree d in the heap must have size at least F_d+2, where F_k is the kth Fibonacci number. The degree bound follows from this and the fact (easily proved by induction) that for all integers, where . (We then have, and taking the log to base of both sides gives as required.)

Consider any node x somewhere in the heap (x need not be the root of one of the main trees). Define size(x) to be the size of the tree rooted at x (the number of descendants of x, including x itself). We prove by induction on the height of x (the length of a longest simple path from x to a descendant leaf), that size(x) ≥ F_d+2, where d is the degree of x.

Base case: If x has height 0, then d = 0, and size(x) = 1 = F₂.

Inductive case: Suppose x has positive height and degree d>0. Let y₁, y₂, ..., y_d be the children of x, indexed in order of the times they were most recently made children of x (y₁ being the earliest and y_d the latest), and let c₁, c₂, ..., c_d be their respective degrees. We claim that c_i ≥ i-2 for each i with 2≤i≤d: Just before y_i was made a child of x, y₁,...,y_i−1 were already children of x, and so x had degree at least i−1 at that time. Since trees are combined only when the degrees of their roots are equal, it must have been that y_i also had degree at least i-1 at the time it became a child of x. From that time to the present, y_i can only have lost at most one child (as guaranteed by the marking process), and so its current degree c_i is at least i−2. This proves the claim.

Since the heights of all the y_i are strictly less than that of x, we can apply the inductive hypothesis to them to get size(y_i) ≥ F_ci+2 ≥ F_(i−2)+2 = F_i. The nodes x and y₁ each contribute at least 1 to size(x), and so we have

A routine induction proves that for any, which gives the desired lower bound on size(x).