算法导论 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$ 个节点）与根节点的左子树的节点个数之和已经超过了 ${\displaystyle \frac{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$。也就是说，$\mathrm{\forall }t,\lfloor n/2\rfloor <t\le n$，均没有后继节点。因此，这一部分节点都是叶节点。