前几天搞单片机，想要用到一个空间复杂度小点的排序算法。找到了堆排序和希尔排序。发现我算法几乎都忘得差不多了...这里就复习记录一下堆相关的东西吧。

堆是什么？

堆是一种完全二叉树。

按照我的理解，如果一棵二叉树从右往左、从下往上数的时候中间没有断档，那这个二叉树就算是完全二叉树（严谨的定义自行百度）。像这样的二叉树就可以很方便地用数组表示。

其中每一个非叶节点和其子节点相比，处在一种排序方式里最靠前的位置。

大家给最常见的比大小的堆取了特殊的名字：从小到大的叫最小堆；从大到小的叫最大堆。

这样的结构有一个好处，堆的根节点的值一定是所有节点中最靠前的。接下来的堆排序和优先队列都是利用的这个性质。

完全二叉树的一些性质

一般可以直接用数组来表示完全二叉树，这里用一个长度为6的数组举例。

可以看到，最后一个非叶节点的下标是2，即。

如果长度变成7，因为整除，结果还是2。

但长度变为5后，2变为叶节点。得到最后一个叶节点是1，公式和实际情况符合（这就不证明了）。

所以说，如果一个用数组表示的完全二叉树长度是，那么其最后一个非叶节点的下标为：

也就是说，非叶节点下标的范围是。可以用这个范围来判断一个节点是否是非叶节点。

再看非叶节点和子节点的关系。

不难看出第个非叶节点的左子节点的下标和右子节点的下标为：

由这个性质可以快速求出各个节点。

由构造堆到堆排序

堆排序的核心思路是首先把序列转化为堆，然后不断取出根节点的值并维持剩余部分的堆结构。最后把取出的值依次排列，就是一个有序的序列了。

要怎么转化并维持一个堆呢？以最大堆为例，先从最简单的情况开始。如果只有一个非叶节点，也就是只有两个或三个节点的情况。那么要做的是选出它们中的最大值，如果最大值不是那个非叶节点，则将非叶节点的值和最大值互换。

由此这个互换操作可以扩展到一般情况：

1. 如果被换的子节点是非叶节点，那么在经过“互换”后被换的子树可能不再是堆，需要对其再做一次“互换”。

2. 如果被换的子节点是叶节点，那么就没有东西可换，直接结束。

3. 如果顶端本身就是最大，就不用再“互换”了，可以直接结束。

这种“互换”似乎被叫做heapify（堆化？）[1]那么后面就叫它堆化好了。根据上文的逻辑可以写出堆化的实现（以最大堆为例）：

当然也可以改成迭代版本，一般编译器应该是不会优化尾递归的，可以少占点内存：

实现了互换之后，就可以把一个数组构造成最大堆了。将所有非叶节点由下往上堆化，即可构造出堆。可以想象一下把大数往上浮的这么个过程，让我联想到了晋级赛，或者说二维情况下的冒泡。下面是实现：

最后是堆排序的实现。实现的思路和选择排序类似，分成了两个区域，已排序区域和未排序区域。每次都把根节点的值和最后一个节点交换位置，然后把末尾变为已排序区，最终得到的就是一个有序的序列了（这里是从小到大）。

最后顺便提一下优先队列

可能看完堆排序后，大家心里应该就由优先队列的雏形了。没错关键点还是这个堆化heapify。

新节点入队后，递归地对其上层节点做heapify就可以维持优先。节点的上层节点为

因此实现代码类似于

至于出队，这个和堆排序中每一步迭代的操作是一致的，就不重复了。

一些参考

阿B不让贴站外链，那就只能贴一个了。