算法导论6.3 Exercises 答案

6.3-1

用数组来表示这个堆的变化（横线标出变化之处）：

\(\begin{aligned} \langle5,3,17,\underline{10},84,19,6,22,9\rangle\\ \langle5,3,17,\underline{22},84,19,6,\underline{10},9\rangle\\ \langle5,3,\underline{19},22,84,\underline{17},6,10,9\rangle\\ \langle5,\underline{84},19,22,\underline{3},17,6,10,9\rangle\\ \langle\underline{84},\underline{22},19,\underline{10},3,17,6,\underline{5},9\rangle \end{aligned}\)

6.3-2

由于\(n>0,h\ge 0\)，因此\(n/2^{h+1}>0\)，那么有\(\lceil n/2^{h+1}\rceil\ge 1\ge 1/2\)。

6.3-3

如果如此迭代循环，那么这个算法是错误的，原因如下：

如果建堆前，最大值恰好在堆中某个叶节点，那么按照这个方式进行建堆，第一次循环完成后，这个叶子节点的值不可能直接上升到根节点（最多只能上升\(1\)个高度）。在剩下的循环中，根节点永远不会被访问到，因此循环完成后，最大值不能上升到根节点处，这违反了最大堆的性质。

6.3-4

考虑使用归纳法进行证明。

令\(n\)个节点的堆中，高度为\(h\)的节点个数为\(f_n(h)\)。

当\(h=0\)时，\(f_n(h)=\lceil n/2 \rceil\)成立。这是利用了题目6.1-8的结论：\(\lfloor n/2\rfloor+1,\lfloor n/2\rfloor+2,\dots,n\)都是叶节点。

当\(h>0\)时，假设当\(h'=0,1,\dots,h-1\)时，\(f_n(h')\le \left\lceil\dfrac{n}{2^{h'+1}}\right\rceil\)均成立。当我们删去这个堆上当前的叶节点后，可以发现，剩下的所有节点高度都下降了\(1\)，剩下的节点一共有\(\lfloor n/2\rfloor\)个，那么删去节点后的树可以套用原来的假设。因此有

\(f_n(h)=f_{\lfloor n/2\rfloor}(h-1)\le\left\lceil\dfrac{\lfloor n/2\rfloor}{2^{(h-1)+1}}\right\rceil \le \left\lceil\dfrac{n/2}{2^{h}}\right\rceil= \left\lceil\dfrac{n}{2^{h+1}}\right\rceil\)

最终原结论成立。