堆 (Heap) 又被为优先队列 (Priority Queue)，通过堆可以按照元素的优先级取出元素，而不是按照元素进入队列的先后顺序取出元素。
这里详细介绍其实现。
简介
堆的一个经典的实现是完全二叉树 (Complete Binary Tree)，这样实现的堆成为二叉堆 (Binary Heap)，二叉树要求前 n-1 层必须填满，第 n 层也必须按照从左到右的顺序被填满。
二叉堆的性质包括了：A) Max Heap 每个子树的 root key 要比两个 child key 大；B) Min Heap 每个子树的 root key 要比两个 child key 小。
但是二叉堆对左右两个元素的大小没有限制，如下以最小堆为例，示例如下。
0/2
/ \
1/31 2/4
/ \ / \
3/17 4/23 5/20 6/10
/ \
7/22 8/8
在校验时，只需要遍历所有含叶子节点的节点，检查是否满足条件即可，叶子节点可以忽略。
PushDown
也有被称为 heapify() 的，就是从上到下保证满足堆的性质，一般用作删除。实际上就是对每个节点，选择 left 和 right 中 key 最小的节点，与该节点进行交换；然后依次类推，例如如下。
0/2
/ \
1/31 2/20
/ \ / \
3/17 4/23 5/4 6/10
/ \
7/22 8/8
将 1 作为起点，最小的是 3/17 ，那么与之交换，成为。
0/2
/ \
1/17 2/20
/ \ / \
3/31 4/23 5/4 6/10
/ \
7/22 8/8
再以被交换的 3 节点，此时需要与 8 交换，变成。
0/2
/ \
1/17 2/20
/ \ / \
3/8 4/23 5/4 6/10
/ \
7/22 8/31
注意，此时只是保证添加的元素满足堆条件，例如 31 已经添加到了合适位置，但是对于 3/8 却不满足条件。也就是说，通过单次 PushDown 操作不一定会同时满足条件。
PushUp
从底层向上，一般用于添加，例如将 4 的 15 替换为 3 ，那么就可以逐层向上检查。
0/4
/ \
1/7 2/10
/ \ / \
3/8 4/3 5/20 6/12
/
7/22
构建
直接通过数组构建时，因为只有一半的节点是有叶子节点的，所以，只需要检查一半的节点确保其满足条件即可，详见 heap_node_max() 实现，例如如下节点，返回 4 。
0
/ \
1 2
/ \ / \
3 4 5 6
/ \ /
7 8 9
构建时执行 PushDown 即可，构建过程以如下示例为例。
----- 原始数组如下
0/12
/ \
1/15 2/20
/ \ / \
3/22 4/2 5/4 6/10
/ \
7/7 8/8
----- 首先从 3 开始
0/12
/ \
1/15 2/20
/ \ / \
3/7 4/2 5/4 6/10
/ \
7/22 8/8
----- 然后检查 2 节点
0/12
/ \
1/15 2/4
/ \ / \
3/7 4/2 5/20 6/10
/ \
7/22 8/8
----- 接着是 1 节点
0/12
/ \
1/2 2/4
/ \ / \
3/7 4/15 5/20 6/10
/ \
7/22 8/8
----- 最后一个 0 节点
0/2
/ \
1/12 2/4
/ \ / \
3/7 4/15 5/20 6/10
/ \
7/22 8/8
Extract
获取根节点，这跟是最大堆还是最小堆有关，移除根节点之后，把最后一个节点放到根节点，移动之后可能会违反堆的特性，所以，需要利用 DownPush 进行检查。
0/2
/ \
1/7 2/4
/ \ / \
3/8 4/15 5/20 6/10
/ \
7/22 8/12
移除第一个节点后，将最后一个节点替换到最开始节点，然后执行 PushDown 操作。
0/12
/ \
1/7 2/4
/ \ / \
3/8 4/15 5/20 6/10
/
7/22
最终结果是。
0/4
/ \
1/7 2/10
/ \ / \
3/8 4/15 5/20 6/12
/
7/22
Insert
只需要添加到最后，然后 PushUp 即可。
Remove
当删除节点的数值时，原来的位置就会出现一个孔，填充这个孔的方法是把最后的叶子的值赋给该孔，并下调到合适位置，最后把该叶子删除。
实现
因为是完全二叉树，通常通过数组完成，对于 n 叉堆来说，下标为 x 的元素，其孩子节点的下标范围是 [nx+1, nx+n]，比如 2 叉堆，下标为 x 的元素，其孩子节点的下标为 2x+1 和 2x+2 。
如下简单以二叉堆作为示例，有如下特点 (中括号假设开始为 1 ，小括号的开始为 0 )：
- 堆的根节点存放在数组位置
array[1] (0)的地方； - 父节点
i的左子节点在位置array[2*i] (2*i+1)； - 父节点
i的右子节点在位置array[2*i+1] (2*i+2)； - 子节点
i的父节点在位置array[floor(i/2)] (floor((i-1)/2))。 - 最多非子节点数为
floor(i/2) floor((i - 1)/2)。
上述的 floor() 表示取整，例如 5/2=2 。在实现时，可以将 0 作为临时存储，那么第一个元素就可以 1 开始。
0 1
/ \ / \
1 2 2 3
/ \ / \ / \ / \
3 4 5 6 4 5 6 7
/ \ / \ / \ / \ / \ / \ / \ / \
7 8 9 10 11 12 13 14 8 9 10 11 12 13 14 15
C 语言格式 正常格式
在实现时，包括了两个主要操作：A) UpHeap 在添加的时候；B) DownHeap 以某个节点从上向下调整，通常删除节点时使用。
基本接口
一般会包含如下的几个接口：
insert()添加元素。extract()获取最大、最小元素。degrade()用于降级某个元素。
其中的更新只是向上增长，例如最小堆是 Decrease 而最大堆是 Increase ，也就是只支持 PushUp 操作，这样可以保证只需要执行该操作即可，而执行 PushDown 可能会违反栈的规则。
总结
如果所有节点还没有满足栈性质，那么针对单个节点执行 PushDown 可能会违反规则，此时需要对所有的非叶子节点执行；而单个节点的 PushUp 操作仍然可以确保满足条件。