排序算法概述：堆排序
堆排序
了解堆数据结构及其在排序中的应用
介绍
堆是一种以二叉树为基础的数据结构，用于表示数组。堆遵循以下结构规则：
- 完全性。堆的每个层级都完全填满元素。然而，最后一个层级可能只有部分元素，从左边开始填充。
- 堆规则。任何父节点的值必须小于或等于其子节点的值。如果满足该属性，则称堆为最小堆。还存在一种最大堆变体，其中父节点的值必须大于子节点的值。
本文中的示例和代码将提供给最小堆。最大堆的算法流程看起来非常相似。下面是一个最小堆的示例。
堆通常以数组的形式存储。如果一个父节点的索引为i，则其左右子节点的位置分别为2 * i + 1和2 * i + 2。相反地，如果一个非根节点的索引为i，则其父节点的索引为(i – 1) // 2。根据这个原则，我们可以得到上面堆的数组表示：
操作
堆支持几种操作：
- 插入节点
- 从数组构建堆
- 提取具有最小值的节点
- 排序
由于堆数据结构有多个操作，更实际的做法是将其实现为一个类。现在，我们将实现其基础功能。每个操作后，都会提供相应的代码片段。
- heap字段以堆的形式存储输入数组（稍后将实现）
- _swap()方法接受数组的两个索引，并交换它们的值。
- _number_of_children()方法返回一个节点的子节点数量（0、1或2）
插入节点
堆的新元素插入到最后的位置。如果新元素小于父节点的值，插入操作可能会破坏堆规则。为了避免这个问题，新节点将递归地向上传播，直到不再违反堆规则为止。这个过程称为堆化（向上堆化）。
从上图中我们插入一个值为3的节点。
- 插入后，由于3 < 15（父节点），堆规则被破坏。我们交换元素3和15。
- 现在节点3有一个值为7的新父节点。同样，由于3 < 7，堆规则不满足。因此，我们交换3和7。
- 节点3位于索引2，并且其父节点的值为1。由于3 ≥ 1，堆规则是正确的。在这个阶段，插入过程结束。
让我们来计算插入的时间复杂度。当需要将新节点从底部传播到树的顶部级别时，最坏情况可能发生。由于任何树的高度与其元素总数N的对数成比例，每个比较都需要O(1)的时间，因此最终的估计结果为O(logN)的时间复杂度。
- insert() 方法将值追加到堆中，然后调用堆化方法将其上升。
- _heapify_up() 方法递归地在父节点上调用自身，直到堆规则正确。
构建堆
对于输入数组的每个元素，都会调用一个插入过程。这就是构建堆的方式。
关于复杂度，构建堆似乎需要 O(N * logN) 的时间，因为对于每个元素，我们调用的函数的时间复杂度为 O(logN)。然而，可以改进这个估计，并且可以数学上证明总时间为 O(N)。
- 对于传入 build() 方法的数组，堆是通过插入调用来构建的。
提取具有最小值的节点
最小节点位于堆的顶部。我们提取最小值并用堆的最后一个节点替换顶部节点。堆规则被违反，所以我们向下传播这个元素。这个算法与我们上面使用的先前算法非常相似（在插入元素时是向上传播的）：在每个步骤中，我们将当前元素与具有最小值的子节点交换。这个过程持续到堆规则不再被破坏或当前元素没有子节点为止。
在上图中，节点值为 1 的节点被提取了，最后一个值为 15 的节点占据了它的位置。
- 由于节点 15 违反了堆规则，我们将其与最小的子节点 3 交换。
- 然后节点 15 有了值为 7 和 8 的子节点。同样，我们将 15 与最小的子节点 7 交换。
- 之后，15 位于索引 5，并且只有一个子节点，即 20。由于 15 ≤ 20，我们停止堆化过程。
与插入部分的堆化算法类似，此算法具有相同的渐进时间复杂度，为 O(logN)。
排序
排序通过提取最小节点来实现。当堆不为空时，我们调用 extract_min() 函数，并将每个最小元素追加到一个新数组中。这样数组将由排序过的元素组成。
由于堆包含 N 个节点，extract_min() 的时间复杂度为 O(logN)，因此总的排序时间复杂度为 O(N * logN)。
结论
我们已经介绍了堆的所有四个主要操作。要使用堆数据结构对数组进行排序，首先需要构建一个堆，然后对其调用排序方法。构建堆需要 O(N) 的时间，排序需要 O(N * logN) 的时间，最终导致堆排序的渐进时间复杂度为 O(N * logN)。
下面是 Heap 类的完整实现。
除非另有说明，所有图片均由作者提供。
