在 Go 中进行堆排序！

堆排序是一种漂亮的排序算法。它使用最大堆对具有定义顺序关系的数字序列或其他元素进行排序。在本文中，我们将深入探讨 Go 标准库堆排序实现。首先，简要回顾一下二进制 max-heaps。max-heap 是一个容器，它在 O（1） 时间内提供其最大元素，在 O（log n） 中添加一个元素，并在 O（log n） 中删除最大元素。最大堆是几乎完整的二叉树，其中每个节点都大于或等于其子节点。在整篇文章中，我将后者称为堆属性。这两个属性共同

定义了最大堆：

在堆算法中，最大堆表示为数组。在数组表示形式中，索引中节点的子节点位于索引 i2*i+1 和 2*i+2 中。

Building a heap 构建堆

数组可以在 O（n） 时间内转换为最大堆。太神奇了，不是吗？

这是算法：将输入数组视为堆。它尚不满足堆属性。从堆的倒数第二层（即叶子上方一级）开始迭代堆的节点，然后返回根目录。对于遇到的每个节点，将其在堆中向下传播，直到它大于其两个子节点。向下传播时，始终与较大的子项交换。

它为什么有效？我会试着用这个挥手的证明来说服你（不过可以随意跳过）：取一个树节点 x 。因为我们从后到前迭代堆，所以当我们到达它时，植根于其两个子项的子树已经满足堆属性。如果 x 大于它的两个子项，我们就完成了。否则，我们会 x 与它最大的孩子交换。这使得子树的新根大于其两个子树。如果不 x 满足其新子树中的堆属性，则该过程将重复，直到它满足或成为叶子，在这种情况下，它将没有任何子项。这适用于堆中的所有节点，包括根节点。堆排序算法现在是主菜——堆排序。堆排序分两步进行：使用我上面显示的算法从输入数组构建最大堆。这需要 O（n） 时间将堆中的元素弹出到输出数组中，从后到前填充它。每次从堆中删除最大元素都需要 O（log n） 时间，对于整个容器来说，这加起来就是 O（n * log n）。Go 实现的一个很酷的特性是，它使用输入数组来存储输出，从而节省了为输出分配 O（n） 内存的需要。堆排序实现Go 排序库支持任何按整数编制索引的集合，其元素具有定义的顺序关系，并支持在两个索引之间交换元素：当然，任何连续的数字容器都可以满足此接口。现在我们来看看它的 heapSort() 正文：该函数的签名有点神秘，但查看前 3 行就可以弄清楚了：

a 并且是 bdata . heapSort(data, a, b) 在半开范围内 [a, b) 排序 data 。

first 是 a 的副本。lohigh 并且是归 a 一化的索引 — lo 始终从零开始，并且 hi 从输入的大小开始。接下来，代码构建

max-heap：// Build heap with greatest element at top.
for i := (hi - 1) / 2; i >= 0; i-- {
siftDown(data, i, hi, first)
}

正如我们之前所看到的，代码从叶子上方的一个级别扫描堆，并用于 siftDown() 向下传播当前元素，直到它满足堆属性。我将在下面更详细地介绍 siftDown() 。在这个阶段， data 是一个最大堆。接下来，我们弹出所有元素以创建排序数组：

// Pop elements, largest first, into end of data.
for i := hi - 1; i >= 0; i-- {
data.Swap(first, first+i)
siftDown(data, lo, i, first)
}

在此循环中， i 是堆中的最后一个索引。在每次迭代中：堆的最大值 first 与堆的最后一个元素交换。堆属性通过向下传播新的 first 属性来恢复，直到它满足堆属性。堆大小 i 减少 1。换句话说，我们从后到前填充数组，从最大的元素开始，到大小上的第二个元素，一直到最小的元素。结果是排序后的输入。维护堆属性在我提到的文章中，我提到使用 siftDown() 来维护堆属性。让我们看看它是如何工作的：此代码将元素 root 一直沿树向下传播，直到它大于其两个子元素。当下降一个级别时，该元素将与其更大的子元素交换。也就是说，要确保新的父节点大于其两个子节点：

前几行计算第一个子项的索引，并检查它是否存在：

child := 2*root + 1
if child >= hi {
break
}

child >= hi 表示电流 root 是一片叶子，所以算法停止了。接下来，我们选择两个孩子中较大的一个：

if child+1 < hi && data.Less(first+child, first+child+1) {
child++
}

由于任何节点的子节点在数组中彼此相邻， child++ 因此选择第二个子节点。接下来，我们检查父项是否确实比子项小：

if !data.Less(first+root, first+child) {
return
}

如果父项大于最大的子项，则完成任务，因此我们返回。最后，如果父元素小于子元素，我们将交换两个元素并递增 root ，为下一次迭代做准备：结论这是我阅读一段不熟悉的代码并尝试解释它的第三篇文章。我喜欢这种体验，因为它教会了我如何阅读代码以及如何就代码进行交流