堆结构简介

1 基本结构

堆类似二叉树，但是是有序的，所谓的有序，就是父节点和子节点有固定的大小关系（即堆属性）。就是父节点大于它的每个子节点的话，此时根节点就是最大的了，这叫最大堆。如果父节点小于它的每个子节点的话，此时根节点就是最小的了，这叫最小堆。

如图，10>7 10>2 7>5 7>1 这是一个最大堆

2 与树的比较

树的内存使用空间比堆高，因为需要存储节点的指向，堆只要一个数组存储就可以了。

对于普通的二叉树，可以使用如下的方式组织数据，

可以看到是允许第三层没有铺满的情况，最右边的节点还是空的。

对于堆的话，是必须要把当前层铺满才能铺下一层的，也就是可能会出现上面这样的结构，但是不会出现上面的二叉树那样没有铺满一层的情况。

3 堆的存储

以这个堆为例，是用数组

[10, 7, 2, 5, 1]

来存储的。实际上堆的堆属性可以满足快速查找某个节点的父子节点的要求。

堆的n个节点存在一个大小为n的数组，数组从前往后，相当于从上到下，从左到右遍历了堆依次存储下了各节点。故很容易得到对于数组中的下标为i的节点，其父节点在数组中的下标为

father = floor((i-1)/2)
leftchid = 2i+1
rightchid = 2i+2

比如10，父节点下标是floor((0-1)/2)=floor(-0.5)=-1，这不是一个有效的数组下标，所以节点10没有父节点，左右节点下标分别是1 2

需要注意下，对于数组中下标为2的节点2，算出来子节点在数组中的下标分别是5 6，但是数组没那么大，说明节点2没有子节点。

显然根据该公式找父子节点非常快，时间是O(1)

4 堆的高度

这个堆的高度是2，有3层。堆的高度就是层数-1

如果一个堆有n个节点，那么其高度h就是floor(log2(n))，计算思路如下：

2^0+2^1+..+2^h>=n
2^(h+1)-1>=n

叶子节点总是位于数组的floor(n/2)和n-1之间

5 堆的操作

主要涉及2个操作，以最大堆为例：

如果节点的值比父节点的值大，那么交换这个节点和它的父节点，这个节点在堆中的位置上升了。

对应的，从父节点的角度看，如果节点的值比子节点的值小，那么需要将这个节点向下移动，这个操作叫堆化（heapify）。

5.1 插入一个节点

以如下的最大堆为例：

插入16的话，在对应的数组后追加

[ 10, 7, 2, 5, 1, 16 ]

对应的树变成了：

发现16比2大，交换16和2:

完了发现16比10大，交换：

这就是最终结果

5.2 删除根节点

堆的设计决定了绝大部分你要删除的是根节点。

最重要的一步就是删除根节点了，根节点由最后一个节点补上，然后不断堆化（因为是从根节点的角度考虑的），最终得到满足堆属性的堆。

举个例子：

删掉10了，取出最后堆对应数组的最后一个元素放到根节点：

发现1比7和2都小，此时交换一个较大的上来，

1<5，再交换：

这就是最终结果

5.3 删除任意节点

将选择的要删除的节点D和最后一个节点P交换，然后删除D，站在P的角度，如果P是子节点，考虑和父节点交换，如果P是有子节点的父节点，考虑堆化。

6 应用场景

总结下来就是需要快速访问到最重要的元素，这时候可以使用堆，把最重要的元素放在根节点

6.1 堆排序

这个看上面图应该就理解了，这里不多赘述了

6.2 优先级队列

优先级队列和一般队列的区别在于，一般队列出的优先级可以理解为进的越早，出的越早，即先进先出。但是优先级队列是按照特定的优先级出去的，谁优先级越高，谁越先出去。那么可以和堆联系起来，可以将优先级最高的放在堆顶，组成一个最大堆，当然组成最小堆也可以，需要看看实际场景中哪种方便。

例子：有100个文件，每个文件大小是100M，每个文件都是由有序字符组成的，现在要将这100个文件组成一个有序的大文件。

其实任意两个文件之间，都是可以比出顺序的，那么就可以决定了谁排在前面，谁排在后面。可以用这100个文件组成一个最小堆，堆的根节点实际上就是大文件最开始的元素，根节点的子节点都是排在它后面的。最后对这个堆从上往下，从左到右逐层遍历，那么就可以得出这个大文件了。

6.3 求topK即前K大元素

问题：在包含n个元素的数组array中，求解前K大元素

排个最小堆，这个堆的大小只要为K即可，可以用数组存储。遍历array，如果发现堆满了，比较当前元素值和最小堆的根节点，比根节点大则替换到根节点，然后调整堆为最小堆。如果堆没满，则将元素最为最后一个节点插入，调整堆为最小堆。

---

本文参考了如下资料：

Heap

堆排序原理及其应用场景