32.堆排序¶

Heapsort是另一种基于比较的算法，它使用堆对数组进行升序排序。本章建立在第22章"堆"中介绍的堆概念之上。

Heapsort利用了堆的优势，根据定义，堆是一个部分排序的二叉树，具有以下特点：

在一个最大堆中，所有的父节点都比它们的子节点大。
在最小堆中，所有的父节点都比它们的子节点小。

下图显示了一个父节点值下划线的堆：

开始工作¶

打开启动器操playground。这个操场已经包含了一个最大堆的实现。你的目标是扩展Heap，使其也能进行排序。在你开始之前，让我们看看一个关于堆排序工作的可视化例子。

示例¶

对于任何给定的未经排序的数组, 要从低到高排序, 堆排序必须首先将这个数组转换成最大堆：

这种转换是通过筛选所有的父节点来完成的，最终在正确的位置。由此产生的最大堆是：

这与下面的array相对应：

因为单个筛下操作的时间复杂度是O(log n)，所以建立一个堆的总时间复杂度是O(n log n)。

我们来看看如何对这个数组进行升序排序。

因为最大堆中最大的元素总是在根部，所以你开始将索引0的第一个元素与索引n - 1的最后一个元素交换。交换后，数组的最后一个元素在正确的位置，但却使堆无效。因此，下一步是对新的根节点5进行筛查，直到它落在正确的位置。

注意，你排除了堆的最后一个元素，因为你不再认为它是堆的一部分，而是排序后的数组的一部分。

由于对5进行了筛选，第二大元素21成为新的根。现在你可以重复之前的步骤，将21与最后一个元素6交换，缩小堆并向下筛选6。

你开始看到一个模式了吗？堆积排序是非常直接的。当你交换第一个和最后一个元素时，较大的元素会以正确的顺序移到数组的后面。你重复交换和筛选的步骤，直到你达到一个大小为1的堆。

然后数组就被完全排序了。

Note

这个排序过程与"第26章"的选择排序非常相似。

实现¶

接下来, 你将实现这个排序算法. 实际的实现非常简单，因为繁重的工作已经由siftDown方法完成：

extension Heap {
  func sorted() -> [Element] {
    var heap = Heap(sort: sort, elements: elements) // 1
    for index in heap.elements.indices.reversed() { // 2
      heap.elements.swapAt(0, index) // 3
      heap.siftDown(from: 0, upTo: index) // 4
    }
    return heap.elements
  }
}

以下是发生的情况：

你首先做了一个堆的副本。在堆排序对elements数组进行排序后，它不再是一个有效的堆。通过在堆的副本上工作，你可以确保堆保持有效。
你循环浏览数组，从最后一个元素开始。
将第一个元素和最后一个元素交换。这个交换将最大的未排序的元素移到它的正确位置。
因为现在的堆是无效的，你必须从新的根节点开始筛选。结果是，下一个最大的元素将成为新的根节点。

Note

为了支持堆排序，你在siftDown方法中加入了upTo参数。这样一来，siftDown只使用数组中未排序的部分，而数组会随着每次循环迭代而缩小。

最后，试一试你的新方法：

let heap = Heap(sort: >, elements: [6, 12, 2, 26, 8, 18, 21, 9, 5])
print(heap.sorted())

这段代码应该打印出来：

[2, 5, 6, 8, 9, 12, 18, 21, 26]

性能¶

尽管你从内存排序中受益，但堆排序的性能在最好、最差和平均情况下都是O(n log n)。这种性能上的统一性是因为你必须遍历整个列表一次，而且每次交换元素时，你都必须执行一次筛分，这是一个O(log n)的操作。

堆排序也不是一个稳定的排序，因为它取决于元素是如何布置和放入堆的。例如，如果你按等级对一副牌进行堆排序，你可能会看到它们的套牌与原来的牌相比改变了顺序。

关键点¶

堆排序利用max heap数据结构对数组中的元素进行排序。
堆排序通过遵循一个简单的模式对其元素进行排序：
1. 交换第一个和最后一个元素。
2. 从根部进行sift-down，以满足作为堆的要求。
3. 将数组的大小减少一个，因为最后的元素将是最大的元素。
4. 重复这些步骤，直到你到达数组的起点。