学习顺序主线第 13 / 22 课 · 阶段 4

为什么现在学:处理优先级由数值决定时,需要第三种取出顺序。

返回算法课程
栈与队列进阶

堆与优先队列Heap

只维护父子之间的局部顺序,就能快速取得全局极值。

40 分钟前置:数组 · 完全二叉树

学完这一课,你应该能做到

  • 由数组下标还原完全二叉树
  • 说明下沉为什么必须选较大的孩子
  • 区分线性建堆与逐项插入的复杂度

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最直接的办法,为什么慢?

每次取最大值都线性扫描剩余元素。

暴力 · O(n) / 次

反复取 k 次时,需要 O(kn) 次检查。

03一步步,推导出优化思路

1

用父子大小关系维护最值

只要求每个父节点不小于它的孩子,根自然就是最大值。

2

较小父值沿较大孩子下沉

用数组存完全二叉树,孩子下标为 2i+1 和 2i+2。

3

从最后一个非叶节点向上建堆

从最后一个非叶子节点向前下沉,自底向上建堆。

贯穿算法的不变量

处理 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;堆保证的是父子关系和根的最值,不是线性数组整体排序。

下沉为何只需修一条路径

  1. 从后往前处理时,当前节点的孩子子树已经是堆。叶子提供基础情形。
  2. 若父值≥较大孩子,它也≥另一个孩子,当前子树直接成立。否则把较大孩子换到父位,它可以支配两边。
  3. 交换只可能破坏原父值落入的那个子树,继续沿该路径下沉。节点不断向叶子前进,最终停下,当前整棵子树成堆。

04让每一步,都看得见

试着先预测下一步,再点击「下一步」验证。变量、动画与代码会同步变化。

Heap交互演示
STEP 01 / 8
3
0
1
1
4
2
2
3

数组表示完全二叉树:父节点 i 的孩子是 2i+1 与 2i+2。

当前处理已处理 / 已确定未处理
01

从左到右观察数组。橙色表示当前比较,绿色表示已确定的位置。

heap.py参考实现 · 当前第 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复杂度,来自具体的工作量

时间复杂度
O(n)O(n)

这是自底向上的建堆复杂度:约 n/2 个节点无需下沉,n/4 个最多下沉 1 层,累加为 O(n)。单次入堆、出堆为 O(log n)。

辅助空间
O(1)O(1)

原地下沉只需几个下标。教学函数复制输入额外占 O(n);堆本身储存 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这些细节,容易踩坑

01

堆不是排序数组

兄弟节点之间没有大小保证。

02

区分大小顶堆

维护最大的 k 个值常用容量 k 的小顶堆,根是当前保留值中最小的。

用反例检查前提

随便选一个更大孩子会留下一处错误

[1,3,5] 的父值 1 小于两个孩子。若先与左边 3 交换并直接结束,得到 [3,1,5],根 3 仍小于右孩子 5,不是最大堆。

怎样修正:每次选较大的孩子,且交换后继续修复被换下去的父值。最小堆则把比较方向反过来。

08把想法带进真实题目

合上答案,自己推一次

堆顶删除以后怎么办

最大堆 [9,7,8,1,2] 删除根 9 后,把末尾 2 放到根并移除最后一格。接下来与哪个孩子交换,结果是什么?

需要一点提示

两个孩子是 7 和 8。

查看完整推导与答案
  1. 替换后是 [2,7,8,1],应选较大的右孩子 8。
  2. 交换得到 [8,7,2,1];2 已到叶子,修复完成。
  3. 先取出了最大值 9,并把剩余元素重新维护成堆。这就是优先队列删除最大值的核心步骤。

完成上面的手算练习,再把思路迁移到这些题目。

09不用背模板,回答这几个问题

01最大堆保证什么?

02自底向上建堆为什么是 O(n)?

03取出堆顶后的修复成本?

你已经走完了这次推导。

能用自己的话解释复杂度和不变量,再标记为掌握。

把知识连起来

继续阅读

本课例子与推导为本站编写。需要另一种表述或进一步学习时,可对照这些公开课程与文档:

MIT 6.006 · 算法讲义Princeton Algorithms · 课程资料

能独立完成本课练习,再标记掌握。也可以直接用上面的链接继续学习。