Leetcode专题 堆结构和堆排序

注意，算法和数据结构里面的堆（Heap）和内存分配里面的堆（Heap）并不是一个概念。内存分配里面的堆的概念更类似于池（Pool）。 Stackoverflow上有一个讨论 ，我们就不细究了。知道我们这里讨论的是算法和数据结构里面的堆就好了。我还是按照《算法导论》的介绍来进行。

所谓堆，就是一个用一维数组来表示一个完全二叉树的这么一个数据结构。所谓二叉树就是一种树，每一个父节点，有最多两个子节点，一般叫做左右子树。

完美二叉树的定义是一个二叉树层数为k的时候，它的元素数量等于2 ^k -1。如下图

而一个完全二叉树可以理解为是一个完美二叉树缺少一部分或者不缺少一部分的二叉树，但是内容一定是从上到下，从左到右的填充，也就是缺少的部分总在右边。如下图：

我们用堆来存储上面这个完全二叉树的话，我们就可以存储为一个数组元素依次为[A, B, C, D, E, F, G, H, I, J, K, L]。虽然完全二叉树不像完美二叉树那样是每一层都完整的。但是因为数组的这个存储方式。我们可以保证的知道，这个二叉树的根节点的索引是1（顺序索引，也就是数组索引的0）。

而任何一个子节点的父节点的索引是子节点的索引整除2。而左子树的根节点是父节点的索引乘2，右子树的根节点是父节点的索引乘2+1。

所以，我们很容易得到子节点和父节点互相访问的函数：

然后，我们可以定义一个数据结构，叫做最大堆（Max-Heap），这个数据结构的特点是每个父节点，都大于自己的子节点，那么我们也知道根节点一定是最大的。下图是一个最大堆，树结构和它在数组中的状态。

你可以简单的想像一个最小堆，其实就是最大堆的一个反面。我们就不细说了。

假设一个最大堆的某个节点比自己的子节点小，这就说明它违反了最大堆的属性，但是他的子节点都是合法的最大堆，我们怎么纠正这个错误，让这个节点恢复成一个合法的最大堆呢？这个操作，我们叫做Max-Heapify，最大堆合法化。操作思路是，我们比较这个节点和它的直接左右子节点，谁大，谁变成新的父节点，也就是当前节点和它最大的直接子节点交换。然后，我们检查这个新的直接子节点，是否比自己的子节点小，如果小也交换。简单的说，就是把一个小的父节点，一步步下沉。我们做了一个视频演示，假设4为一个错误的节点。

这个逻辑转换成代码如下_A是类内存存储数组，索引减一是因为数组索引从0开是，我们之前聊的都是顺序索引：

为了实现Max-Heapify过程，我们写了一个辅助函数exchange：

然后，假设我们从一个完全不符合最大堆原则的二叉树出发如何能够见一个最大堆呢？假设我们有如下的堆：

我们的方法是从堆的中间（也就是5这个位置）出发，往回一个一个节点的进行Max-Heapify操作，结束后，这个堆就是最大堆了。下面是演示视频：

简单的描述就是从堆的中间点到根节点，调用Max-Heapify操作即可，代码如下：

我们仔细观察最大堆结构的时候，可能有一个结论是，最大堆不是一个有完全顺序的数据结构。虽然每个父节点都大于自己的子节点。但是左子树的根不见得大于或者小于有右子树的根。我们不能直接用二叉树的任何遍历方式得到一个有序数组。那么我们怎么用堆来 排序 呢。我们可以首先获得堆的根节点，然后根节点和最后一个节点互换，然后我们缩小堆，让刚才被换到最后一个位置的原来的根节点从堆中被移除。然后我们Max-Heapify堆的根节点，保证堆仍旧是一个合法的堆，然后我们取堆的根节点。

也就是说，我们知道堆的根节点一定是最大的，我们把它放到最后面。这时候破坏了堆，我们不管取出来的那个数（缩小堆），我们Max-Heapify堆，然后堆根节点又是最大的了。这样我们就一步步找到了最大数，把他们排列在后面，直到最后我们就获得了一个从小到大的数组。也就是说最大堆适合从小到大排序，如果要从大到小排序我们就需要用到最小堆了。排序要从一个合法的最大堆出发。我们刚才构建了一个合法的最大堆。我们用它来做演示：

下面是演示视频：

代码如下：

堆还可以支持的一个操作是把当前的堆顶返回，然后缩小堆。这跟堆排序的思想一样，但是可以解决我们只想知道最大值，或者最大几个值，而不需要全部排序的需求。代码可以写为：

最后总结一下，堆是一个完全二叉树的一维数组表示法。顺序索引满足1即为根节点，子节点索引乘2即为父节点，父节点除2为左子节点，除2然后+1为右子节点。使用Max-Heapify操作我们可以让一个子节点合法，但是本身不合法的节点，变成合法的最大堆。我们从一个非最大堆中间开始降序循环调用Max-Heapify，可以让其变为最大堆。我们把最大堆的顶点和底互换，然后缩小堆，合法化堆，如此循环到最大堆消失，可以实现数组的顺序排序。

那么，最大堆的第一个功能是用来实现排序，堆排序。第二个功能，如果我们的目标不是完全排序，而是想找到最大数，或者最大k个数，那么用堆比全部排序开销更低一些。

下面是LeetCode的最大堆和堆排序相关题目：