数据结构与算法 / 系统课时
二叉堆与优先队列
二叉堆与优先队列
二叉堆用数组保存一棵完全二叉树,并通过局部堆序让最小值或最大值始终位于堆顶。本课以稳定任务队列为主示例,说明数组映射、入堆、出堆和相同优先级处理。
学习目标
- 理解完全二叉树的数组表示与父子索引关系
- 区分最小堆、最大堆和完整排序
- 能使用
heapq构建同优先级保持先来先服务的任务队列
结构与堆序
二叉堆首先是一棵完全二叉树,因此可以紧凑地存入数组。对索引 i,左子节点索引是 2 * i + 1,右子节点索引是 2 * i + 2,父节点索引是 (i - 1) // 2。
最小堆要求每个父节点不大于它的子节点,所以最小元素位于数组下标 0;最大堆则相反。堆只保证父子之间的局部顺序,数组整体通常不是升序结果。

稳定优先队列示例
Python 的 heapq 提供最小堆,数值越小越先出队。若只存 (priority, task),优先级相同时 Python 会继续比较任务对象,既不能保证加入顺序,也可能因对象不可比较而报错。加入递增序号后,元组按“优先级、序号”排序,任务对象不再参与比较。
python
import heapq
from itertools import count
queue = []
sequence = count()
def add_task(priority, name):
# 序号用于保持同优先级任务的加入顺序
heapq.heappush(queue, (priority, next(sequence), name))
add_task(3, "生成报表")
add_task(1, "处理支付回调")
add_task(2, "发送通知")
add_task(1, "记录告警")
print("当前最高优先级:", queue[0][2])
while queue:
priority, _, name = heapq.heappop(queue)
print(f"执行: {name}, 优先级: {priority}")预期输出:
text
当前最高优先级: 处理支付回调
执行: 处理支付回调, 优先级: 1
执行: 记录告警, 优先级: 1
执行: 发送通知, 优先级: 2
执行: 生成报表, 优先级: 3操作复杂度与边界
查看堆顶只访问数组首元素,时间复杂度为 。插入时新元素先放到数组末尾,再向上调整;删除堆顶时把末尾元素移到顶部,再向下调整,两者都是 。查找任意指定值仍可能遍历整个堆,复杂度为 。
使用相反数可以在 heapq 上模拟最大堆。直接修改堆中间元素会破坏堆序,应重新堆化,或使用新的条目配合延迟删除策略。需要取最大的若干元素时,应根据数据规模选择固定大小最小堆,而不是先完整排序所有数据。
按自己的节奏,确认真正理解。