12.1. 堆排序¶

我们对快速排序的讨论是从考虑用 BST 排序的实用性开始的。 BST 比其他排序方法需要更多空间，而且由于向树中插入值的代价相对较高， 它会比快速排序或归并排序更慢。 BST 也有可能变得不平衡，从而导致 \(\Theta(n^2)\) 的最坏情况运行时间。 BST 中的子树平衡与快速排序的划分步骤密切相关。 快速排序的轴值所起的作用大致相当于 BST 的根值：左划分（子树）存储小于 轴值（根值）的值，而右划分（子树）存储大于或等于轴值（根值）的值。

我们可以基于一种更适合该用途的树结构，设计出一个好的排序算法。 具体来说，我们希望这棵树是平衡的、空间高效的且快速的。 该算法应当利用这样一个事实：排序是一种专用应用，所有待存储的值在开始时 就已经全部可用。 这意味着我们不一定需要一次一个地把值插入树结构中。

堆排序 基于 堆 数据结构。 堆排序具备刚才列出的全部优点。 完全二叉树是平衡的，其数组表示是空间高效的，而且我们可以一次性把所有值 装入树中，从而利用高效的 buildheap 函数。 当所有记录的键值都唯一时，堆排序在最好、平均和最坏情况下的渐近性能 都是 \(\Theta(n \log n)\) 。 它在平均情况下不如快速排序快（相差一个常数因子），但堆排序有一些特殊 性质，使它特别适用于 外排序 算法，用于对大到无法装入主存的数据集进行排序。

Settings

Saving...
Server Error
Resubmit

完整实现如下。

void heapsort(int[] A) {
  // The heap constructor invokes the buildheap method
  MaxHeap H = new MaxHeap(A, A.length, A.length);
  for (int i = 0; i < A.length; i++) {  // Now sort
    H.removeMax(); // Removemax places max at end of heap
  }
}

void heapsort(T[] A) {
  // The heap constructor invokes the buildheap method
  MaxHeap<T> H = new MaxHeap<T>(A, A.length, A.length);
  for (int i=0; i<A.length; i++) {  // Now sort
    H.removeMax(); // Removemax places max at end of heap
  }
}

void heapsort(Comparable* A[], int n) {
  std::cout << "Getting started with array:" << std::endl;
  for (int j = 0; j<n; j++)
    std::cout << *A[j] << " ";
  std::cout << std::endl;
  MaxHeap H(A,n,n);
  std::cout << "Now, ready to unpack the heap" << std::endl;
  for (int i = 0; i < n; i++)
     H.removemax();
}

下面是一个堆排序热身练习。

12.2. 堆排序熟练度练习¶

现在测试一下你对堆排序的理解程度。 你能重现它的行为吗？

12.3. 堆排序分析¶

这个可视化展示了堆排序的运行时间分析。

Settings

Saving...
Server Error
Resubmit

虽然堆排序通常比快速排序慢一个常数因子 （因为用 removemax 卸下堆比快速排序的一系列划分要稍慢一些）， 但堆排序相比目前研究过的其他排序有一个特殊优势。 建堆相对廉价，只需 \(\Theta(n)\) 时间。 从堆中删除最大值的记录在最坏情况下需要 \(\Theta(\log n)\) 时间。 因此，如果我们想找出数组中键值最大的 \(k\) 条记录，可以在 \(\Theta(n + k \log n)\) 时间内完成。 如果 \(k\) 很小，这比用前面介绍的其他排序方法找出 \(k\) 条最大 值记录所需的时间有显著改进（其中许多方法都需要先对整个数组排序）。 有一种情形可以利用这个概念，那就是 Kruskal 算法 在 最小代价生成树 的实现中。 该算法要求按升序访问各条边（因此要使用最小堆），但一旦 MST 构建完成， 这个过程就立即停止。 因此，只需对相对较小一部分边进行排序。

另一种特殊情况是，所有待排序记录的键值都相同。 这代表了堆排序的最好情况。 这是因为删除最大值只需常数时间，因为被交换到顶部的值永远不会沿堆向下筛选 （由于所有键值都相等）。 这一过程会重复进行，以常数时间从堆中删除 \(n\) 个元素，因此最好情况 总时间为 \(\Theta(n)\) 。