算法导论6.1 Exercises 答案

6.1-1

最少为\(2^h\)，最多为\(2^{h+1}-1\)。

一棵高度为\(h\)的满二叉树一共有\(2^h-1\)个节点。

因此，在一棵高度为\(h-1\)的满二叉树上多添加一个节点，就成为了一棵高度为\(h\)的二叉树，故最少为\(2^h\)。

一棵高度为\(h\)的满二叉树则对应着最多的情况，即\(2^{h+1}-1\)个节点。

6.1-2

由题目6.1-1可知，对于任意\(n\)个节点的堆，存在高度\(h\)使得\(2^h\le n\le 2^{h+1}-1\)，即\(2^h\le n<2^{h+1}\)。

对等式两边对\(2\)取对数，得到\(h\le \lg n< h+1\)。因此可以得到\(h=\lfloor\lg n\rfloor\)。

6.1-3

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

当一棵子树只有一个节点（没有后代）时，这棵子树的最大元素是这个节点的元素，因此原结论成立。

当一棵子树有多个节点时，假设这个子树的根的直系后代各自的子树都满足这个结论。那么根据最大堆的定义，父亲节点的元素必须大于等于子节点的元素，可以得出，这个子树的根节点的元素都大于等于其子树内的所有元素。

因此原结论得证。

6.1-4

它将会出现在任意一个叶节点之中。

6.1-5

第\(k\)大的节点至少可以放在第\(1\)层的\(A[3]\)位置。根据这个堆结构的性质不难看出，根节点（\(1\)个节点）与根节点的左子树的节点个数之和已经超过了\(\dfrac{n}{2}\)，并且\(k\)已经满足\(2\le k\le \lfloor n/2\rfloor\)，因此先将第\(1\sim k-1\)大的元素按照堆的性质在这一部分放置好，然后再将第\(k\)大的元素放置在\(A[3]\)，再将接下来的其它数按照堆的性质进行放置即可。

第\(k\)大的节点至多可以放在第\(\min\{k-1,\lfloor\lg n\rfloor\}\)层。放置方式如下：从根节点到这个节点的路径上，分别是第\(1\)大，第\(2\)大，……，第\(k\)大的值。

6.1-6

是的，因为对于任意\(i \ge 2\)，PARENT(i) <= i总成立。如果数组\(A\)是已经排序的，那么就有A[PARENT(i)] <= A[i]，这满足了最小堆的性质。

6.1-7

不是，因为\(A[4]=15,A[9]=16\)，不满足A[PARENT(9)] <= A[9]。

6.1-8

对于二叉堆中的所有非根节点\(t=2,3,\dots,n\)，它们的父节点是\(\lfloor t/2\rfloor\)，即\(1,1,2,2,\dots,\lfloor n/2\rfloor\)。也就是说，\(\forall t,\lfloor n/2\rfloor< t \le n\)，均没有后继节点。因此，这一部分节点都是叶节点。