算法导论6.4 Exercises 答案

6.4-1

完成建堆后，数组变成$\langle25,13,20,8,7,17,2,5,4\rangle$。

在排序过程中，用数组来表示这个堆的变化（横线标出变化之处）：

$\begin{aligned}
\langle\underline{25},13,20,8,7,17,2,5,4\rangle\
\langle \underline{20},13,\underline{17},8,7,\underline{4},2,5|25\rangle\
\langle \underline{17},13,\underline{5},8,7,4,2|20,25\rangle\
\langle \underline{13},\underline{8},5,\underline{2},7,4|17,20,25\rangle\
\langle \underline{8},\underline{7},5,2,\underline{4}|13,17,20,25\rangle\
\langle \underline{7},\underline{4},5,2|8,13,17,20,25\rangle\
\langle \underline{5},4,\underline{2}|7,8,13,17,20,25\rangle\
\langle \underline{4},\underline{2}|5,7,8,13,17,20,25\rangle\
\langle 2,4,5,7,8,13,17,20,25\rangle\
\end{aligned}$

6.4-2

初始化：在第$n$次循环开始前，堆已经建好，满足最大堆的情况，所有$n$个最小的数都在里面；数组$A[n+1:n]$为空，包含$0$个最大元素，已经是有序的。

保持：完成了第$k$个值$A[k]$和最大堆的值$A[1]$的交换后，那么现在数组$A[k:n]$是$A$中最大的$n-k+1$个数，并且将堆的大小减少了$1$，保证属于堆的部分和已排序部分不相交。交换完成后，此时只有根节点可能并不满足最大堆的性质，调用一次MAX-HEAPIFY(A, 1)即可使得$A[1:k-1]$保持最大堆的性质。$A[k:n]$一部分是有序的。

终止：堆中只剩下$1$个最小值，已排序部分则是$n-1$个最大的数。因此最终整个序列是有序的。

6.4-3

两者的的时间复杂度均为$O(n\lg n)$。建堆后，那么只考虑单次的MAX-HEAPIFY操作为$O(\lg n)$。整个过程运行时间为$O(n\lg n)$。