数据结构与算法： 二叉堆
堆
堆（英语：Heap）是计算机科学中的一种特别的树状数据结构。若是满足以下特性，即可称为堆：“给定堆中任意节点 P 和 C，若 P 是 C 的母节点，那么 P 的值会小于等于（或大于等于） C 的值”。若母节点的值恒小于等于子节点的值，此堆称为最小堆（min heap）；反之，若母节点的值恒大于等于子节点的值，此堆称为最大堆（max heap）。在堆中最顶端的那一个节点，称作根节点（root node），根节点本身没有母节点（parent node）。
堆始于 J._W._J._Williams 在 1964 年发表的堆排序（heap sort），当时他提出了二叉堆树作为此算法的数据结构。堆在戴克斯特拉算法（英语：Dijkstra’s algorithm）中亦为重要的关键。
在队列中，调度程序反复提取队列中第一个作业并运行，因为实际情况中某些时间较短的任务将等待很长时间才能结束，或者某些不短小，但具有重要性的作业，同样应当具有优先权。堆即为解决此类问题设计的一种数据结构。
注： 解决这类问题的一个方法就是将队列中的任务按照一定的规则进行排序，并且在队列中的任务发生变化（第一个已经被执行，即顶部被删除）后仍能快速排序。比如时间段的优先其实就是要构建一个小根堆，按优先级应该是要构建大根堆。
二叉堆
简介
二叉堆(binary heap) 故名思议是一种特殊的堆，二叉堆具有堆的性质（父节点的键值总是大于或等于（小于或等于）任何一个子节点的键值），二叉堆又具有二叉树的性质（二叉堆是完全二叉树或者是近似完全二叉树）。
二叉堆多数是以数组作为它们底层元素的存储，按照从堆的顶点开始从上往下，从左往右放到数组中。设数组为a[0...n-1]我们会发现非叶子节点的 i 的左右子节点(存在)在数组中的位置分别为i*2+1、i*2+2。而在数组中最后一个非叶子节点的位置可以表示为 n/2-1 (n为数组的大小)。借助这些我们可以实现小根堆与大根堆的形成，同时也能实现堆排序。
1
2
3
4
5
6
10
/ \
15 56 10 | 15 | 56 | 25 | 30 | 70
/ \ /
25 30 70
(a) 二叉堆结构 (b) 数组存储结构
1
2
3
4
5
6
70
/ \
56 30 70 | 56 | 30 | 25 | 15 | 10
/ \ /
25 15 10
(a) 二叉堆结构 (b) 数组存储结构
特点
二叉堆通常支持以下操作：删除，插入节点,创建二叉堆。这些操作复杂对都是\( O(\mathbf{log}_{2}n) \)。也可以支持查找 O(n) 复杂度。
二叉堆是专门为取出最大或最小节点而设计点数据结构，这种数据结构在查找一般元素方面性能和一般数组是没有多大区别的。二叉堆在取出最大或最最小值的性能表现是O(1)，取出操作完成之后，二叉堆需要一次整形操作，以便得到下一个最值，这个操作复杂度 \( O(\mathbf{log}_{2}n) \)。这是一个相当理想的操作时间。
但是二叉堆也有一个缺点，就是二叉堆对存储在内存中的数据操作太过分散，这导致了二叉堆在cpu高速缓存的利用与内存击中率上面表现不是很好，这也是一个二叉堆理想操作时间所需要付出的代价。
使用范围
二叉堆主要的应用击中在两个地方一个是排序，一个是基于优先级队列的算法。比如：
- A*寻路
- 统计数据（维护一个M个最小/最大的数据）
- huffman code（数据压缩）
- Dijkstra’s algorithm（计算最短路径）
- 事件驱动模拟（粒子碰撞。这个比较有意思，从国外的一个网站看到过）
- 贝叶斯垃圾邮件过滤（这个只是听过没怎么了解）
二叉堆的实现
插入
当我们要在二叉堆中插入一个元素时我们通常要做的就是有三步：
- 把要插入的节点放在二叉堆的最末端
- 把这个元素和它的父节点进行比较，如果符合条件或者该节点已是头结点插入操作就算完成了
- 如果不符合条件的话就交换该节点和父节点位置。并跳到第
2步。
假设我们有一个如下的最大二叉堆，X代表节点插入位置，我们要插入的值是15，则步骤如下：
1
2
3
4
5
11
/ \
5 8
/ \ /
3 4 X
我们插入的位置为 X，其父节点为8，由于X（15）大于 8 于是 8 与 15 互换。
1
2
3
4
5
11
/ \
5 15 <----
/ \ /
3 4 8 <----
X(15)接着和11比较，发现15比11大于是互换。
1
2
3
4
5
15 <----
/ \
5 11 <----
/ \ /
3 4 8
15 已经是头结点操作插入操作结束。
插入节点不停向上比较的过程叫做向上整形。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void insert(Data data)
{
if(_last_index==0) //我们的数组从index 1，我们用第一个插入的数填充index 0.
{
_array.push_back(key);
}
_array.push_back(data); //将key插入数组最末
swim_up(++_last_index); //对最后一个插入的数字进行向上整形
}
void swim_up(size_type n) //向上整形
{
size_type j; //n 代表向上整形的元素，j代表n的父节点
while( (j = n / 2) > 0 && compare(_array[n], _array[j]) ) //判断n父节点是否为空&比较n与j大小
{
exchange(n, j);
n=j;
}
}
删除
按定义，堆中每次都删除第0个数据。也就是最小或者最大的元素。为了便于重建堆，实际的操作是将最后一个数据的值赋给根结点，然后再从根结点开始进行一次从上向下的调整。调整时先在左右儿子结点中找最大的，如果父结点比这个最小的子结点还大说明不需要调整了，反之将父结点和它交换后再考虑后面的结点。相当于从根结点将一个数据的“下沉”过程。，删除操作分为三步：
- 首先将头结点与最后一个节点位置互换（互换之后的最后一个节点就不再视为二叉堆的一部分）。
- 将互换之后的新的头结点与子节点进行比较，如果符合条件或者该节点没有子节点了则操作完成。
- 将它和子节点互换，并重复步骤
2。（如果它的两个子节点都比它大/小，那么它与其中较大/小的一个互换位置。最大堆的话与较大的互换，最小堆的话与较小的互换。）
假设我们有如下一个最大堆：
1
2
3
4
5
11
/ \
5 8
/ \ / \
3 4 7 6
现在我们删除头结点 11，我们将 11 头结点与最末一个节点 6 互换。互换之后我们剔除了最后一个节点。我们将 6 与它的子节点进行比较，发现它小于右子节点8，不满足条件跳到步骤 3。
1
2
3
4
5
6
/ \
5 8
/ \ /
3 4 6
将节点6 与其子节点中较大值进行互换。在跳到步骤 2,发现 6 依然小于子节点 7。 跳到步骤3, 将 6与 7 互换。后跳到步骤 2 结束。
1
2
3
4
5
8 8
/ \ / \
5 6 ==> 5 7
/ \ / / \ /
3 4 7 3 4 6
注: 删除时之所以要将最后一个节点放到顶点位置进行调整，是由于这样调整后如果之前是一颗完全二叉树的话，删除完后依然是一颗完全二叉树。否则假设直接从根的直接点中选择最大或最小节点上移的方式，删除完成后可能不是一颗完全二叉树。比如上例中，如果直接从子节点中选择进行上移操作的话，结果如下, 最终不是一颗完全二叉树:
1
2
3
4
5
11 8 8
/ \ / \ / \
5 8 ==> 5 X ==> 5 7
/ \ / \ / \ / \ / \ \
3 4 7 6 3 4 7 6 3 4 6
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
const T& get_min() //不允许修改值，这样会造成堆被破坏.
{
return _array[1];
}
void pop_min() //如果没有数据在队列中，这个行为是未定义的.
{
_array[1]=_array[_last_index--];
_array.pop_back();
sink_down(1);
}
void sink_down(size_type n)
{
size_type j; //j 是 n的子节点的索引
while( ( j = 2 * n) <= _last_index )
{
if( j + 1 <= _last_index && _compare(_array[j+1],_array[j]) ) //比较两个子节点,取出其中较小的.
j=j+1;
if( _compare(_array[j],_array[n]) ) //较小的子节点与父节点进行比较
exchange(n,j);
n=j;
}
}
创建
如果元素数组的初始排列是{53，17，78，9，45，65，87，23}，现在把它视为完全二叉树的顺序存储，从编号最大的分支结点i=⌈(n-2)/2⌉=⌈(7-2)/2⌉=3开始（⌈x⌉表示对向上取整, 见为什么从i=⌈(n-2)/2⌉开始循环），轮流以i=3,2,1,0为根，将它们控制的子树调整为小根堆，其过程如下所示：
1.从 0 开始编号，按顺序生成的二叉树
1
2
3
4
5
6
7
53(0)
/ \
17(1) 78(2)
/ \ / \
9(3) 45(4) 65(5) 87(6)
/
23(7)
2.从 ⌈i=(n-2)/2⌉=3 开始，将其调整为小根堆。由于 9 小于其所有子节点 23，满足小根堆性质，无需调整。
1
2
3
4
5
6
7
53(0)
/ \
17(1) 78(2)
/ \ / \
9(3) 45(4) 65(5) 87(6)
/
23(7)
3.调整 i=2 节点 78。 78 > 65 所以将两节点互换。 互换后满足小根堆要求。
1
2
3
4
5
6
7
53 53
/ \ / \
17 78 17 65
/ \ / \ ==> / \ / \
9 45 65 87 9 45 78 87
/ /
23 23
4.调整 i=1 节点 17。 17 > 9将节点两节点互换，互换后满足条件。
1
2
3
4
5
6
7
53 53
/ \ / \
17 65 9 65
/ \ / \ ==> / \ / \
9 45 78 87 17 45 78 87
/ /
23 23
5.调整 i=0 节点 53。 (a) 53 > 9将节点两节点互换。（b）互换后 53 大于其两个子节点，所以需要继续互换。 两个子节点 17 < 45 , 所以选取 53 与 17 互换。(c) 互换后 53 > 23,再将两节点互换。互换后 53没有子节点，完成。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
53 9
/ \ / \
9 65 (a) 53 65 (b)
/ \ / \ ==> / \ / \ ==>
17 45 78 87 17 45 78 87
/ /
23 23
9 9
/ \ (c) / \
17 65 ==> 17 65
/ \ / \ / \ / \
53 45 78 87 23 45 78 87
/ /
23 53
可以看到所有节点满足小根堆性质后，最小值在二叉树的根节点位置。但是其余节点间并不是完全按照从小到大的顺序排列的，比如节点 i=7为 53，但是 i=6的节点为 87。所以并不是越后面的节点的值越大。
大根堆的构建过程同理。
堆排序
堆排序其实分为以下几步：
- 首先将待排序的
n个元素构建一个二叉堆array[n] - 执行删除操作，只是这里我们并不是删除头结点，而是将头结点换到二叉堆末尾，并形成一个除去队列末尾的新二叉堆。
- 重复步骤
2，直到删除了最后一个元素。
这个过程其实就是先构建一个最大/最小二叉堆，然后不停的取出最大/最小元素（头结点），插入到新的队列中，以此达到排序的目的。
topN 问题
topn 指的是从已经存在的数组中，找出最大（或最小）的前n个元素。
topn算法实现思路（找最大的n个元素）:
- 取出数组的前
n个元素，创建长度为n的小根堆。 - 从
n开始循环数组的剩余元素，如果元素a比小根堆的根节点大，将a设置成最小堆的根节点，并让堆保持最小堆的特性。 - 循环完成后，最小堆中的所有元素就是需要找的最大的
n个元素。
该方法的原理其实就是：
- 先取数组前
n个元素，构造小根堆； - 去剩余元素和前面的小根对的跟节点进行比较，根节点是n个数中最小值，所以，如果当前节点比这个最小值小，那么就用当前值替换最小值。然后在重置小根堆，找到堆中新的最小值。
- 循环完成后，小根堆中就是前n个最大值。
求top n个最小值同理，只是将构造的小根堆修改为大根堆即可。
A*寻路
这里只是举一个相对于来说比较简单的例子，用 A* 寻路来解决8-PUZZLE(8格数字拼图)，当然更为经典的一种是15-puzzle，它们道理都是一样的。下面来看看这个问题的描述。
在一个九宫格里面，有1-8 8个数字和一个空格，我们可以移动空格上下左右相邻的数字到空格，然后通过这种移动方式我们最终要求9宫格里面的数字，形成1-8的顺讯排列。类似如下
1
2
3
4
5
1 3 1 3 1 2 3 1 2 3 1 2 3
4 2 5 => 4 2 5 => 4 5 => 4 5 => 4 5 6
7 8 6 7 8 6 7 8 6 7 8 6 7 8
初始 第1次移动 第2次移动 第3次移动 第4次移动
这个问题在我小时候玩图片拼板的时候很难，几乎很久都拼不成功，但是我们只要找到决窍就行了。有两种诀窍是广泛使用的一种称作Hamming priority function，而另外一种就是Manhattan priority function。这里我们使用更为广泛使用的Manhattan方法作为讲解。
Manhattan方法：我们用这个9宫格里面每个数字到达自己指定位置的距离加上我们目前总共移动的步数来表示一个度量值 M。这里所指的每个数字到达自己指定位置的距离指的是通过横向移动和纵向移动到达自己规定位置的距离。举例：
1
2
3
1 3
4 2 5
7 8 6
在这里图中数字 1 在位置1上于是距离为 0。数字 3 到达自己的指定位置需要右移一步于是距离为 1，4 在位置4上于是距离为0，2 需要向上移动一步到达自己的制定位置距离为1，5 需要左移一步距离为1，7,8 在指定位置上距离0，6需要向上移动一步距离1，于是这个图形的总距离为 4。
我们从上图的 初始 状态开始，有两种移动方法，一种是 3 移动到空格，一种是 5 移动到空格。我们应该选择哪种移动方法呢，这个时候就需要使用我们刚才所说的度量值了，我们选择度量值小的一种移动方式。3 移动到空格的方法距离3，移动步数1，度量值M=4。5 移动到度量空格的距离5，移动步数为1，度量值M=6。我们选择 3 移动到空格的这种方式。这里的具体过程是我们把记录下 3 和 5 移动的这两种节点的父节点，然后分别计算他们的 M 值，然后放入到min bianry heap中，取出最小 M 值节点作为移动节点，并从 min binary heap 中删除这个节点。
1
2
3
4
5
1 3 1 3 5
4 2 5 4 2
7 8 6 7 8 6
"3"移动到空格，M=4 “5”移动到空格，M=6
当我们选出了第一次的移动节点之后，我们就要在第一次的移动节点上再决定下一次的移动节点，下一次怎么走一共有 3+1 种节点，3 种是基于上一次移动后我们新加入的移动节点，1 种是上一次我们并没有沿用的移动节点，我们计算 3 种新节点的 M 值并记录他们的父节点然后再把它们加入取出最小的作为下一次的移动节点，直到我们得到距离等于 0 的节点位置。
当我们找到距离等于 0 的节点之后，我们递归查找该节点父节点直到查找到根节点位置，这个查找的顺续的逆序便是我们移动节点到达最终目的地的顺序
这里有一个 A* 寻路中需要注意的地方，我们并不会删除我们没有沿用的节点，而是仍然留住它在 min binary heap 中作为备选节点以防现有路线不是最优解或是不能到达终点。
这种数字拼盘程序还有一种非常值得注意的地方，即是这种数字拼盘总是存在着一种无法求解的可能，比如 8-puzzle 中，这种排序和它的变种都无法解：
1
2
3
1 2 3
4 5 6
8 7
面对这种难题，有一种较为合理的解决方法来判断，我们只需要交换我们初始节点中同一排的相邻两个节点位置（两个都为非空节点）得到另外一种初始化节点，在这两种方案中只有一种方案能够解。所以我们只需要同时计算两种初始节点，只要其中一个得出解了那么另外一个即可以判断是无解的了。
好奇的你或许会问为什么交换了同一排相邻的两个非空节点的位置之后，新得到的节点的可解性与旧节点的可解性相反。这个问题严谨的数学解释需要参考较早的研究论文，并且对于非专业学生也比较晦涩难懂。我能想到的比较容易解释方式及是“同一排两个节点交换了位置之后，你永远也无法通过移动还原到交换前的模样”。这也即是
1
2
3
1 2 3 1 2 3
4 5 6 得不到=> 4 5 6 的原因。
8 7 7 8
为什么从i=⌈(n-2)/2⌉开始循环
首先 ⌈x⌉ 表示对 x 向上取整。⌊x⌋ 表示对 x向下取整。比如 ⌈1/2⌉=1, ⌊1/2⌋=0。
创建二叉堆的时候，先形成完全二叉树，然后从 i=⌈(n-2)/2⌉ 开始调整，为什么从这个节点开始调整呢？我们看一下完全二叉树的结构：
1
2
3
4
5
6
7
0
/ \
1 2
/ \ / \
3 4 5 6
/ \ / \ / \
7 8 9 10 11 12
可以发现当树节点从 0 开始编号的时候，对于任意的一个节点 P假设其编号为 i。如果其存在子节点，那么其左子节点 LC 的编号为 2i+1, 其右子节点 RC 的编号为 2i+2。
由此可知对于任意子节点 C, 其编号为 n
- 如果其为左子节点， 则其父节点为
(n-1)/2 - 如果其为右子节点， 则其父节点为
(n-2)/2
当节点编号为偶数时为右子节点, 所以 (n-2)/2 为整数。
当节点编号为奇数时为左子节点，其父节点为 (n-1)/2,该值与 (n-2)/2 向上取整相等。比如 n=13, 其父节点为 (n-1)/2=(13-1)/2=6, ⌈(n-2)/2⌉=⌈(13-2)/2⌉=⌈11/2⌉=6。
综上，对任意节点C如果编号为 i, 其父节点的编号一定为 ⌈(i-2)/2⌉。在二叉堆中，最大节点编号为 n, 从 ⌈(n-2)/2⌉ 节点开始进行调整，意思就是从最后一个有子节点的节点开始调整。
