Skip to content

19.4 Bounding the maximum degree

19.4-1

Professor Pinocchio claims that the height of an nn-node Fibonacci heap is O(lg⁡n)O(\lg n). Show that the professor is mistaken by exhibiting, for any positive integer nn, a sequence of Fibonacci-heap operations that creates a Fibonacci heap consisting of just one tree that is a linear chain of nn nodes.

  • Initialize: insert 33 numbers then extract-min.
  • Iteration: insert 33 numbers, in which at least two numbers are less than the root of chain, then extract-min. The smallest newly inserted number will be extracted and the remaining two numbers will form a heap whose degree of root is 11, and since the root of the heap is less than the old chain, the chain will be merged into the newly created heap. Finally we should delete the node which contains the largest number of the 3 inserted numbers.

19.4-2

Suppose we generalize the cascading-cut rule to cut a node xx from its parent as soon as it loses its kkth child, for some integer constant kk. (The rule in Section 19.3 uses k=2k = 2.) For what values of kk is D(n)=O(lg⁡n)D(n) = O(\lg n)?

Following the proof of lemma 19.1, if xx is any node if a Fibonacci heap, x.degree=mx.degree = m, and xx has children y1,y2,…,ymy_1, y_2, \ldots, y_m, then y1.degree≥0y_1.degree \ge 0 and yi.degree≥i−ky_i.degree \ge i - k. Thus, if sms_m denotes the fewest nodes possible in a node of degree mm, then we have s0=1,s1=2,…,sk−1=ks_0 = 1, s_1 = 2, \ldots, s_{k - 1} = k and in general, sm=k+∑i=0m−ksis_m = k + \sum_{i = 0}^{m - k} s_i. Thus, the difference between sms_m and sm−1s_{m - 1} is sm−ks_{m - k}.

Let {fm}\{f_m\} be the sequence such that fm=m+1f_m = m + 1 for 0≤m<k0 \le m < k and fm=fm−1+fm−kf_m = f_{m - 1} + f_{m - k} for m≥km \ge k.

If F(x)F(x) is the generating function for fmf_m then we have F(x)=1−xk(1−x)(1−x−xk)F(x) = \frac{1 - x^k}{(1 - x)(1 - x - x^k)}. Let α\alpha be a root of xk=xk−1+1x^k = x^{k - 1} + 1. We'll show by induction that fm+k≥αmf_{m + k} \ge \alpha^m. For the base cases:

fk=k+1≥1=α0fk+1=k+3≥α1⋮fk+k=k+(k+1)(k+2)2=k+k+1+k(k+1)2≥2k+1+αk−1≥αk. \begin{aligned} f_k & = k + 1 \ge 1 = \alpha^0 \\ f_{k + 1} & = k + 3 \ge \alpha^1 \\ & \vdots \\ f_{k + k} & = k + \frac{(k + 1)(k + 2)}{2} = k + k + 1 + \frac{k(k + 1)}{2} \ge 2k + 1+\alpha^{k - 1} \ge \alpha^k. \end{aligned}

In general, we have

fm+k=fm+k−1+fm≥αm−1+αm−k=αm−k(αk−1+1)=αm.f_{m + k} = f_{m + k - 1} + f_m \ge \alpha^{m - 1} + \alpha^{m - k} = \alpha^{m - k}(\alpha^{k - 1} + 1) = \alpha^m.

Next we show that fm+k=k+∑i=0mfif_{m + k} = k + \sum_{i = 0}^m f_i. The base case is clear, since fk=f0+k=k+1f_k = f_0 + k = k + 1. For the induction step, we have

fm+k=fm−1−k+fm=k∑i=0m−1fi+fm=k+∑i=0mfi.f_{m + k} = f_{m - 1 - k} + f_m = k \sum_{i = 0}^{m - 1} f_i + f_m = k + \sum_{i = 0}^m f_i.

Observe that si≥fi+ks_i \ge f_{i + k} for 0≤i<k0 \le i < k. Again, by induction, for m≥km \ge k we have

sm=k+∑i=0m−ksi≥k+∑i=0m−kfi+k≥k+∑i=0mfi=fm+k.s_m = k + \sum_{i = 0}^{m - k} s_i \ge k + \sum_{i = 0}^{m - k} f_{i + k} \ge k + \sum_{i = 0}^m f_i = f_{m + k}.

So in general, sm≥fm+ks_m \ge f_{m + k}. Putting it all together, we have

size(x)≥sm≥k+∑i=kmsi−k≥k+∑i=kmfi≥fm+k≥αm. \begin{aligned} size(x) & \ge s_m \\ & \ge k + \sum_{i = k}^m s_{i - k} \\ & \ge k + \sum_{i = k}^m f_i \\ & \ge f_{m + k} \\ & \ge \alpha^m. \end{aligned}

Taking logs on both sides, we have

log⁡αn≥m.\log_\alpha n \ge m.

In other words, provided that α\alpha is a constant, we have a logarithmic bound on the maximum degree.