01先从一个问题出发
不断有新任务到来,每次总要选最紧急的任务。无需每次把全部任务排好序。
把 [3,1,4,2] 建成最大堆。
只维护取最大值所需的顺序
如果不断问当前最大值,每次全排序做了多余工作。最大堆只要求每个父节点不小于它的孩子,于是沿祖先链向上,根节点一定不小于所有后代。左右子树之间没有排序要求。
完全二叉树按层从左到右填满,可以直接存进数组:下标 i 的左、右孩子为 2i+1、2i+2,父节点为 floor((i−1)/2)。例如 [3,1,4,2] 中,3 是根,1、4 是孩子,2 是 1 的左孩子。
从叶子往上修,避免重复返工
叶子没有孩子,天然满足堆条件。从最后一个非叶节点 floor(n/2)−1 向前处理,轮到某个父节点时,它的两个子树已经分别成堆。只需把这个父值向下沉到合适位置。
若两个孩子都比父值大,必须选较大的那个交换。这样新的父值才能同时盖过两个孩子。交换后,只有被换下去的原父值可能继续违反其子树的条件,沿着这一条路径继续修即可。
02最直接的办法,为什么慢?
每次取最大值都线性扫描剩余元素。
反复取 k 次时,需要 O(kn) 次检查。
03一步步,推导出优化思路
用父子大小关系维护最值
只要求每个父节点不小于它的孩子,根自然就是最大值。
较小父值沿较大孩子下沉
用数组存完全二叉树,孩子下标为 2i+1 和 2i+2。
从最后一个非叶节点向上建堆
从最后一个非叶子节点向前下沉,自底向上建堆。
处理 start 时,它的左右子树已经是堆;下沉后以 start 为根的树也是堆。
拿一个小输入,逐步手算
把 [3,1,4,2] 建成最大堆。
| start / root | 检查 | 数组 | 结论 |
|---|---|---|---|
| 1 / 1 | 孩子下标 3,值 2>1 | [3,2,4,1] | 以 1 为根的子树成堆 |
| 0 / 0 | 两个孩子 2、4,选择 4 | [4,2,3,1] | 4 到根,原 3 下沉 |
| 0 / 2 | 下标 2 已是叶子 | [4,2,3,1] | 最大堆完成 |
[4,2,3,1] 不是降序排列,2 后面还有 3;堆保证的是父子关系和根的最值,不是线性数组整体排序。
下沉为何只需修一条路径
- 从后往前处理时,当前节点的孩子子树已经是堆。叶子提供基础情形。
- 若父值≥较大孩子,它也≥另一个孩子,当前子树直接成立。否则把较大孩子换到父位,它可以支配两边。
- 交换只可能破坏原父值落入的那个子树,继续沿该路径下沉。节点不断向叶子前进,最终停下,当前整棵子树成堆。
04让每一步,都看得见
试着先预测下一步,再点击「下一步」验证。变量、动画与代码会同步变化。
数组表示完全二叉树:父节点 i 的孩子是 2i+1 与 2i+2。
从左到右观察数组。橙色表示当前比较,绿色表示已确定的位置。
动画展示参考实现的执行轨迹。切换语言时,当前操作会定位到对应代码行。
代码里的每个关键决定
for start in range(len(a) // 2 - 1, -1, -1):- 从最后一个非叶节点开始。所有下标≥n//2 的节点都是叶子,不需要修复。
if child + 1 < len(a) and a[child + 1] > a[child]:- 先确认右孩子存在,再选两个孩子中较大的。不能默认所有节点都有两个孩子。
root = child- 继续追踪被换下去的原父值,而不是重新从根开始。每次向下推进一层。
05复杂度,来自具体的工作量
这是自底向上的建堆复杂度:约 n/2 个节点无需下沉,n/4 个最多下沉 1 层,累加为 O(n)。单次入堆、出堆为 O(log n)。
原地下沉只需几个下标。教学函数复制输入额外占 O(n);堆本身储存 n 个元素。
把工作量具体数出来
单次插入的上浮或删除根后的下沉,最多经过树高 O(log n);查看根为 O(1)。
自底向上建堆不是 n 次都走 log n 层。大约一半节点是叶子不动,四分之一最多动一层,八分之一最多动两层;求和 n/4×1+n/8×2+…=O(n)。
原地迭代下沉只保留常数个下标,辅助空间 O(1)。参考函数复制输入为 O(n)。若逐项插入 n 次建堆,则最坏 O(n log n),是另一种构建过程。
06看到什么,应该想到它?
这些特征值得停下来想一想:
07这些细节,容易踩坑
堆不是排序数组
兄弟节点之间没有大小保证。
区分大小顶堆
维护最大的 k 个值常用容量 k 的小顶堆,根是当前保留值中最小的。
随便选一个更大孩子会留下一处错误
[1,3,5] 的父值 1 小于两个孩子。若先与左边 3 交换并直接结束,得到 [3,1,5],根 3 仍小于右孩子 5,不是最大堆。
怎样修正:每次选较大的孩子,且交换后继续修复被换下去的父值。最小堆则把比较方向反过来。
08把想法带进真实题目
堆顶删除以后怎么办
最大堆 [9,7,8,1,2] 删除根 9 后,把末尾 2 放到根并移除最后一格。接下来与哪个孩子交换,结果是什么?
需要一点提示
两个孩子是 7 和 8。
查看完整推导与答案
- 替换后是 [2,7,8,1],应选较大的右孩子 8。
- 交换得到 [8,7,2,1];2 已到叶子,修复完成。
- 先取出了最大值 9,并把剩余元素重新维护成堆。这就是优先队列删除最大值的核心步骤。
完成上面的手算练习,再把思路迁移到这些题目。
09不用背模板,回答这几个问题
01最大堆保证什么?
02自底向上建堆为什么是 O(n)?
03取出堆顶后的修复成本?
你已经走完了这次推导。
能用自己的话解释复杂度和不变量,再标记为掌握。