CLRS 第二部分

CLRS

练习

6.4-5

考虑对一个大小 n=2h−1n=2^h-1 的数组进行堆排序时，从堆顶依次取出第 1 大至第 2h−12^{h-1} 大的元素的过程，所有这些元素都需要从所在位置移动到堆顶。一个元素向上移动有两种方式，一种是 MAX-HEAPIFY\mathrm{MAX\text{-}HEAPIFY} 时与父节点交换，另一种是作为当前的最后一个元素直接与堆顶交换。想要通过第二种方式向上移动，这个元素在交换前必须位于第 hh 层，而在这一过程中，原本不在第 hh 层的元素不会被移动到第 hh 层，因此对于前 h−1h-1 层中的元素，它们只能通过第一种方式向上移动。

一个元素通过第一种方式向上移动到堆顶至少需要堆顶到它的距离的时间。前 h−1h-1 层中，前 2h−12^{h-1} 大的元素至少有 2h−22^{h-2} 个，而要使所有这些距离的和最小，它们需要尽量集中在最上面的几层中，此时的距离和是 20×0+21×1+⋯+2h−3×(h−3)+1×(h−2)=2h−2(h−3)+2 2^0\times 0+2^1\times 1+\cdots+2^{h-3}\times (h-3)+1\times (h-2)=2^{h-2}(h-3)+2 即 T(n)>n4(lg⁡n−3)T(n)> \frac{n}{4}(\lg n-3)。

对于任意的 nn，令 n′=2⌈lg⁡(n+1)⌉−1>n/2n'=2^{\lceil\lg (n+1)\rceil}-1>n/2，T(n)≥T(n′)>T(n/2)=n8(lg⁡n−4)=Ω(nlog⁡n)T(n)\ge T(n')>T(n/2)=\frac{n}{8}(\lg n-4)=\Omega(n\log n)。

思考题