优先级队列：需求与动机
看透普通队列的三大根本缺陷，明白消息队列为何而生
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
优先级队列：需求与动机
看透普通队列的三大根本缺陷，明白消息队列为何而生
生活场景：急诊室分诊
用急诊室分诊类比引入优先级概念
普通队列 vs 优先级队列
左右两列对比同一组任务：到达顺序一致，离开顺序完全不同。
优先级队列的核心定义
急诊室里，心梗病人排在普通感冒前面——并非他来得更早，而是病情更重。上一节用场景说明了『为什么需要』，这一页把它上升为数据结构层面的定义：出队顺序由优先级决定，而非到达时间。
头等舱先登机对应高优先级先出队；同舱按排队顺序对应平局回退 FIFO
两种主要实现方式
左路是无序数组，右路是堆结构，对照看它们在插入与取最值上的代价差异。
数组实现：简单但低效
数组实现优先级队列的操作流程，看似简单却藏着代价。
堆实现：高效的结构
从插入新元素开始，沿「父子比较—必要时交换」的上浮路径，看堆如何用 O(log n) 维护顺序。
实现方式对比总结
两种方式都能实现优先级队列，但代价完全不同。选错了，复杂度从 O(log n) 退化成 O(n)。
- 入队 O(1)，但取最小需遍历 O(n)
- 连续内存，无额外指针开销
- 数据量小、极少取最值时
- 入队 O(log n)，取最小也是 O(log n)
- 树形结构，需维护父子关系
- 数据量大、频繁取最值时
核心操作接口
分诊台一天要做三件事：把刚到的病人挂到名单上、按病情严重程度叫下一个、随时确认现在排第一的是谁。优先级队列对外就只暴露这三个动作。
护士挂号=入队，叫号=出队，瞄排队表=查看队首
接口实现示例
用 Python 把上一页的核心接口落地为可运行代码。
对照上页接口：push 调 heappush 维护堆序，pop/peek 都取 _heap[0]（堆顶），is_empty 仅查长度。
需求与动机要点回顾
- ✓优先级改变了'谁先出去'的规则
- ✓本质是在简单性和效率之间做取舍
- ✓数据规模决定选哪种实现
- ✓接口设计是普通队列的自然延伸
课后思考
先独立思考，再看参考答案——重点不是答案对不对，是你的思考路径清不清晰。
参考答案普通队列严格按入队顺序，无法处理「插队」。优先级队列的本质：每次取出的不一定是「最老」的，而是「最重要」的。
参考答案手机通知按重要性分级、外卖按距离/评分派单、OS按进程优先级调度CPU。判断维度都是「重要性」而非「先来后到」。
参考答案退化成普通队列 FIFO。堆的实现反而浪费——O(log n) 的优势完全用不上，按时间顺序处理就够了。