数据结构与算法 / 系统课时

二叉堆与优先队列

二叉堆与优先队列

二叉堆用数组保存一棵完全二叉树,并通过局部堆序让最小值或最大值始终位于堆顶。本课以稳定任务队列为主示例,说明数组映射、入堆、出堆和相同优先级处理。

学习目标

  • 理解完全二叉树的数组表示与父子索引关系
  • 区分最小堆、最大堆和完整排序
  • 能使用 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

操作复杂度与边界

查看堆顶只访问数组首元素,时间复杂度为 O(1)O(1)。插入时新元素先放到数组末尾,再向上调整;删除堆顶时把末尾元素移到顶部,再向下调整,两者都是 O(log⁡n)O(\log n)。查找任意指定值仍可能遍历整个堆,复杂度为 O(n)O(n)。

使用相反数可以在 heapq 上模拟最大堆。直接修改堆中间元素会破坏堆序,应重新堆化,或使用新的条目配合延迟删除策略。需要取最大的若干元素时,应根据数据规模选择固定大小最小堆,而不是先完整排序所有数据。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

二叉堆与优先队列

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通