19.4 Bounding the maximum degree

19.4-1

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

Initialize: insert $3$ numbers then extract-min.
Iteration: insert $3$ 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 $1$, 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 $x$ from its parent as soon as it loses its $k$th child, for some integer constant $k$. (The rule in Section 19.3 uses $k = 2$.) For what values of $k$ is $D(n) = O(\lg n)$?

Following the proof of lemma 19.1, if $x$ is any node if a Fibonacci heap, $x.degree = m$, and $x$ has children $y_1, y_2, \ldots, y_m$, then $y_1.degree \ge 0$ and $y_i.degree \ge i - k$. Thus, if $s_m$ denotes the fewest nodes possible in a node of degree $m$, then we have $s_0 = 1, s_1 = 2, \ldots, s_{k - 1} = k$ and in general, $s_m = k + \sum_{i = 0}^{m - k} s_i$.

Let

$$ f_m = \begin{cases} 0 & m = 0, \\ 1 & 0 < m < k, \\ f_{m - 1} + f_{m - k} & m \ge k. \end{cases} $$

Let $\alpha$ be a root of $x^k - x^{k - 1} = 1$, i.e. $x^{k - 1}(x - 1)=1$. We'll show by induction that $f_{m + k} \ge \alpha^m$.

For the base cases:

$$ \begin{aligned} f_k & = f_{k - 1} + f_0 = 1 + 0 = 1 = \alpha^0 \\ f_{k + 1} & = f_k + f_1 = 1 + 1 \ge \alpha^1 \\ & \vdots \\ f_{k + k} & = f_{2k - 1} + f_k = f_{2k - 1} + 1 \ge 1 + \alpha^{k - 1} = \alpha^k. \end{aligned} $$

In general, we have

$$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 $f_{m + k} = 1 + \sum_{i = 0}^m f_i$. The base case is clear, since $f_k = f_0 + 1 = 0 + 1$. For the induction step, we have

$$f_{m + k} = f_{m - 1 + k} + f_m = 1 + \sum_{i 0}^{m - 1} f_i + f_m = 1 + \sum_{i = 0}^m f_i.$$

Observe that $s_i \ge f_{i + k}$ for $0 \le i < k$. Again, by induction, for $m \ge k$ we have

$$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, $s_m \ge f_{m + k}$. Putting it all together, we have

$$ \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 k + \sum_{i = 0}^m f_i - \sum_{i = 0}^{k - 1} f_i \\ & = k + \sum_{i = 0}^m f_i - (k - 1) \\ & = 1 + \sum_{i = 0}^m f_i \\ & = f_{m + k} \\ & \ge \alpha^m. \end{aligned} $$

Taking logs on both sides, we have

$$\log_\alpha n \ge m.$$

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

And I think $k$ should only satisfy $\alpha > 1$ in $\alpha^{k - 1}(\alpha - 1) = 1$.