08. 堆与优先队列

0. 本章先解决什么问题

普通队列按进入顺序处理:

先进先出

但很多场景要按优先级处理:

先处理最小截止时间
先处理最高优先级任务
先取当前最短路径候选
先合并最小文件块

堆和优先队列解决的问题是:

如何快速拿到当前最大或最小元素?

本章讲二叉堆、堆数组表示、上浮下沉、优先队列应用和限制。

这张图怎么读

这张图说明堆为什么常用数组存完全二叉树:父子关系可以直接用下标计算,堆顶就是当前最优元素。插入靠上浮维护堆序,删除堆顶靠下沉恢复不变量。

1. 优先队列是什么

优先队列不是按插入顺序出队,而是按优先级出队。

操作:

常见成本:

2. 堆的不变量

以小根堆为例:

每个父节点 <= 它的子节点

示意:

1
/
3 5
/ \ /
7 8 9

堆只保证:

堆顶是最小值

它不保证整个数组有序。

3. 完全二叉树和数组存储

堆通常用数组存储完全二叉树。

index: 0 1 2 3 4 5
value: 1 3 5 7 8 9

下标关系:

left(i) = 2i + 1
right(i) = 2i + 2
parent(i) = (i - 1) / 2

好处:

• 不需要节点指针。
• 内存连续。
• cache 更友好。
• 找父子节点只要算下标。

4. 插入:上浮

插入新元素时,先放到数组末尾。

放到最后
与父节点比较
如果比父节点更优,交换
继续向上

这个过程叫上浮。

高度是 O(log n),所以插入是 O(log n)。

5. 删除堆顶:下沉

删除堆顶时:

取出根节点
把最后一个元素放到根
与更优的孩子比较
如果不满足堆序,交换
继续向下

这个过程叫下沉。

每次向下一层,最多走树高,所以是 O(log n)。

6. 建堆

如果有一组无序数据,要建成堆。

方法 1:

逐个插入
O(n log n)

方法 2:

从最后一个非叶子节点开始向前下沉
O(n)

第二种更高效,因为大量底层节点下沉距离很短。

手推:为什么自底向上建堆可以是 O(n)

直觉上,每个节点下沉最多 O(log n),好像 n 个节点就是 O(n log n)。但自底向上建堆时,大多数节点离叶子很近,下沉不了几层。

可以按高度估算:

总成本近似是:

n/4 + n/4 + 3n/16 + …

这个级数不会长成 n log n,而是被一个常数倍的 n 控住。这个推导能帮你避免一个常见误判:建堆不是“把每个元素都插入一次”的同义词;批量建堆可以利用完全二叉树底层节点多、可下沉距离短的结构特性。

7. 堆排序

堆可以用于排序。

思路:

建堆
不断取出堆顶

复杂度:

O(n log n)

特点:

• 不需要额外大量空间。
• 最坏时间稳定。
• 但局部性和常数不一定比其他排序好。

实际排序通常要综合数据规模、稳定性、缓存和常数。

8. 堆不擅长什么

堆擅长拿堆顶,不擅长:

如果需要按 id 删除或更新优先级,通常要额外结构配合,比如映射位置或延迟删除。

机制深挖:优先级更新为什么麻烦

堆只保证父子之间满足堆序,并不记录“某个业务 id 在数组的哪个位置”。如果你想更新某个任务的优先级,会遇到两个问题:

所以实际优先队列经常不是单独一个堆,而是:

• heap:按优先级取最值
• map:按 id 找位置或记录最新版本
• valid/version:判断堆顶是否过期

这就是数据结构组合的典型例子:堆解决“取当前最优”,映射解决“按身份定位”,版本号解决“旧元素失效”。

9. 延迟删除

优先队列里常见问题:

旧任务还在堆里
但它已经被取消或更新

可以不立刻从堆中删除,而是:

弹出堆顶时检查是否有效
无效就丢弃
继续弹

这叫延迟删除。

适合:

• 删除任意元素成本高。
• 无效元素数量可控。
• 弹出时能判断有效性。

延迟删除也有风险:如果取消或更新很多,但很少弹出,堆里会堆积大量无效元素。此时要考虑定期清理、容量阈值重建,或者改用支持定位删除的结构。

故障指纹:优先队列结果不对时先查不变量

堆相关 bug 通常表现得很隐蔽:堆顶看起来偶尔不对、任务重复执行、取消任务仍被执行、定时器突然积压。排查时先分四类。

优先队列的排障核心是:堆只维护“堆顶最优”这个不变量,不维护全局排序,也不会自动理解业务状态。

10. 常见应用

堆的核心能力是:

动态集合中反复取最值。

11. 联系实际:Top K 怎么选结构

要从大量数据里找最大的 K 个。

如果全部排序:

O(n log n)

如果维护一个大小为 K 的小根堆:

遍历每个元素
如果堆未满,入堆
如果新元素大于堆顶,替换堆顶

成本:

O(n log K)

当 K 远小于 n 时更合适。

小实验:手推一次 Top K

目标:从一串数里找最大的 3 个。

数据: 9, 1, 7, 3, 12, 4, 10
K = 3

维护一个大小为 3 的小根堆:

最后堆里就是最大的 3 个元素。这个过程说明:

堆顶不是最终最大值,而是“当前 Top K 中最小的守门员”。

当新元素连守门员都打不过,就不可能进入 Top K。

12. 学完本章你能解决什么问题

学完这一章,你应该能解决或开始分析这些问题:

1. 优先队列和普通队列有什么区别?
2. 堆为什么能 O(1) 查看最值?
3. 堆为什么用数组存完全二叉树?
4. 上浮和下沉如何维护堆序?
5. 建堆为什么可以 O(n)?
6. 堆为什么不适合快速查找任意元素?
7. 延迟删除适合什么场景?
8. Top K、定时器、最短路为什么常用堆?

堆的价值不在“排序”,而在动态过程中快速拿到当前最优元素。

延伸阅读

• from - zero · data-structures