算法导论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)\)。