堆
复习
- 二叉树：每个节点最多两个子节点
- 数组：连续存储，可按下标访问
- 树：用父子关系表示层次
TL;DR
- 堆是一种近似完全二叉树，并满足堆序
- 最小堆中，父节点不大于它的子节点
- 它只保证局部顺序，不保证整体有序
- 用数组就能紧凑地表示堆
正文
二叉搜索树追求“整体有序”，但有时候我们并不需要全部有序，只想要一件事：随时能快速拿到最大或最小的元素。 为此而生的结构，就是堆（heap）。
只守一条局部规则
堆是一种特殊的二叉树，通常用最小堆（min-heap）来说明：它要求每个父节点都不大于它的子节点。
注意，它只约束父与子，亲戚之间、兄弟之间没有要求。所以堆里除了“根是最小的”，其他节点的相对顺序是模糊的。这和二叉搜索树“左小右大、整体有序”完全不同。堆用更弱的规则，换来了更低的维护成本。
反过来，如果要求父节点不小于子节点，就是最大堆（max-heap），根是最大值。
用数组装下整棵树
堆一般是“完全二叉树”：除最后一层外都填满，最后一层从左往右连续填。这个形状有个绝妙的好处：它可以用数组紧凑地存放，不需要任何指针。
因为节点位置有规律，用下标就能算出父子关系：
下标 i 的左孩子：2i + 1
下标 i 的右孩子：2i + 2
下标 i 的父节点：(i - 1) / 2
所以堆既是一棵树，又是一段连续的内存，既省空间又对缓存友好。
插入与取出
堆的两个关键操作，都围绕“保持那条局部规则”展开：
- 插入：先把新元素放到最后，再让它不断和父节点比较、必要时“上浮”，直到位置合适
- 取出堆顶：拿走根之后，把最后一个元素移到根上，再让它和较小的孩子交换、“下沉”，直到恢复规则
这两个操作都只沿着一条路径走，代价是 O(log n)。而看一眼堆顶（最大或最小值），则是 O(1)。
正是这种“随时拿到最值”的能力，让堆成为下一章优先队列的天然实现。
思考题 1
堆为什么只保证“父不大于子”，而不要求整体有序？
思考题 2
为什么堆可以用数组紧凑表示，而普通二叉树不行？
小结
知识点
- 堆是满足堆序的近似完全二叉树
- 最小堆：父不大于子；最大堆：父不小于子
- 只保证局部顺序，堆顶是最值
- 用数组表示，父子位置可用下标计算
参考资料
- Wikipedia(zh)：堆 (数据结构)：满足堆序的树形结构
- Wikipedia(zh)：二叉堆：用数组表示的完全二叉树堆
思考题答案（仅供参考）
思考题 1
因为堆的目标只是“快速拿到最值”，这只需要保证根是最值即可，无需维持整体的全序。规则越弱，插入删除时的调整就越少，维护成本更低。要整体有序，那是二叉搜索树的任务。
思考题 2
因为堆是完全二叉树：除最后一层外都填满、最后一层从左到右连续。这种规整的形状让节点位置可以按层依次编号，父子关系能用下标公式算出来，因此能直接放进数组。普通二叉树形状不规则，位置无法用简单下标对应，只能用指针连接。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪