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\). Thus, the difference between \(s_m\) and \(s_{m - 1}\) is \(s_{m - k}\).
Let \(\\{f_m\\}\) be the sequence such that \(f_m = m + 1\) for \(0 \le m < k\) and \(f_m = f_{m - 1} + f_{m - k}\) for \(m \ge k\).
If \(F(x)\) is the generating function for \(f_m\) then we have \(F(x) = \frac{1 - x^k}{(1 - x)(1 - x - x^k)}\). Let \(\alpha\) be a root of \(x^k = x^{k - 1} + 1\). We'll show by induction that \(f_{m + k} \ge \alpha^m\). For the base cases:
In general, we have
Next we show that \(f_{m + k} = k + \sum_{i = 0}^m f_i\). The base case is clear, since \(f_k = f_0 + k = k + 1\). For the induction step, we have
Observe that \(s_i \ge f_{i + k}\) for \(0 \le i < k\). Again, by induction, for \(m \ge k\) we have
So in general, \(s_m \ge f_{m + k}\). Putting it all together, we have
Taking logs on both sides, we have
In other words, provided that \(\alpha\) is a constant, we have a logarithmic bound on the maximum degree.
本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供,附加条款亦可能应用