算法导论 - 堆排序

Introduction to Algorithms (third edition)

第六章：Heapsort

基于比较的排序主要有插入排序、归并排序、堆排序和快速排序。插入排序和归并排序之前的章节已有介绍，堆排序综合了插入排序和归并排序的优点，最坏情况下的时间复杂度是O(nlgn)，需要的额外空间是O(1)。堆排序使用的是大顶堆：任何节点的值都比它的子节点的值大。注意本章讨论的树，最底层高度为0，往上逐渐增加。

建堆是从最底层的非叶子节点开始，往根节点循环，这样每次处理的节点的子树都是大顶堆，只需将该节点放到合适的位置即可。建堆需要遍历upper(n/2)个节点，处理每个节点的时间复杂度是O(lg(n))，确切的说是O(h)，建堆的时间复杂度是O(n)，而不是O(nlg(n))。证明之前，需要用到一个推论：高度为h的层至多有upper(n/2^{h+1})个节点。这可以通过归纳法来证明。由此，建堆的复杂度是\sum_{h=0}^{lower(lg(n))}(n/2^{h+1})O(h) = O(n * \sum_{h=0}^{lower(lg(n))} h/2^h，由于\sum_{h=0}^{infinite} h/2^h = 2，因此复杂度为O(n)

堆排序就是利用前面的建堆算法，然后每次选出最大值再调整堆，时间复杂度是O(nlg(n)). 堆排序的一个用处就是优先队列，这个可以用在操作系统的进程调度等领域。

堆排序是一个非常有想象力的算法，最坏情况下的时间复杂度是O(nlg(n))，这点比快速排序要好，但是由于它的常数比较大，所以实际应用也不太多，可能更多的还是优先队列的应用领域。重点是要知道分析建堆的时间复杂度和排序的时间复杂度，以及堆的调整算法等。

6.1-1

满二叉树时最多，为2^{h+1} - 1，当第0层只有一个叶子节点时最少，为2^h

6.1-2

由2^h <= n <= 2^{h+1} - 1可以推得h <= lg(n) <= h+1，因此n = lower(lg(n))

6.1-3

这就是大顶堆的性质好不好……

6.1-4

只能是在叶子节点，因为叶子节点的值总是会小于它对应的内节点的值

6.1-5

是。因为所有节点的值都比子节点的值小

6.1-6

不是。7不能是6的子节点

6.1-7

lower(n/2)不能是叶子节点，否则最大的节点只可能是2*(lower(n/2) - 1) + 1 = n - 1，小于n；lower(n/2)+1必须是叶子节点，否则它的子节点至少是2 * (lower(n/2) + 1) = n + 2，大于n。因此lower(n/2)+1是第一个叶子节点

6.2-3

nothing will happen...

6.2-4

叶子节点，没有子节点，nothing will happen...

6.2-5

while i <= A.heap-size/2

6.2-6

heapify the root node, and propagates to bottom, the height is lg(n)

6.3-3

通过归纳法证明，比较复杂，略

6.4-3

都是O(nlg(n))

6.4-4

这么废话嘛……

6.4-5

很显然的，但是严格的证明就不显然了……

6.5-4

保证调用HEAP-INCREASE-KEY的时候key > A[i]，因为不知道A[i]的值究竟是什么

6.5-6

while i > 1 and A[PARENT(i)] < key

    A[i] = A[PARENT(i)]

    i = PARENT(i)

A[i] = key

6.5-7

use a global priority value

for FIFO queue, when in, use the priority value, and decrease it by 1; when out, choose the element with the largest priority value, that is A[1], and heapify;

for stack, when in, use the priority value, and increase it by 1; when out, choose the element with the largest priority value, that is A[1], and heapify.

6.5-9

用k个lists的第一个元素建堆，每次取出最大值，并将对应list的下一个值放入堆顶，调整堆，显然建堆的代价是O(k)，每次调整的代价是O(lgk)，有n个元素需要排序，因此时间复杂度是O(k) + O(nlg(k)) = O(nlg(k))

Problem 6-1

a. 不是，考虑数组[1, 2, 3]，BUILD-MAX-HEAP结果是[3, 2, 1]，而BUILD-MAX-HEAP'结果是[3, 1, 2]

Problem 6-2

a. PARENT(i) = lower((i-2)/d + 1), CHILD(i, j) = d(i-1) + j + 1

b. lg(n) / lg(d)

c. like HEAP-EXTRACT-MAX, but needs to compares to all d children, running time is O(d * lg(n) / lg(d))

d. running time is O(h) = O(lg(n)/lg(d))

e. same...

Problem 6-3

a. [[2, 3, 4, 5], [8, 9, 12, 14], [16, INF, INF, INF], [INF, INF, INF, INF]]

b. Y[1, 1] is the smallest value, while Y[m, n] is the largest value

c. take out Y[1, 1], then compare Y[1, 2] with Y[2, 1], choose the smaller, recursively run on the rest tableaus

d.

e. EXTRACT-MIN takes O(2n) = O(n) times, n^2 numbers, so the sorting time is O(n^3)

f. start from left-bottom most or right-top most