优先级队列的基本实现
看穿两种底层结构如何撑起优先级队列的操作与权衡
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
优先级队列的基本实现
看穿两种底层结构如何撑起优先级队列的操作与权衡
向量的结构与特性
上页选定了数组作为优先级队列的底层容器，但这只是表层决定。这一页拆开向量看：它的结构与特性到底是什么，又凭什么能撑起入队与出队的需求？
凭票号能直接定位，但中间有人离场，后面整排要往前挪一格
向量的入队操作
入队两步走：先追加到末尾，再向上修复堆序。
向量的出队操作
出队的核心：先线性扫一遍找最大值，再用末尾覆盖加 pop_back 完成删除。
向量实现的性能瓶颈
看上下两条路径的对比：入队一步到位，出队却要扫描加移动两段代价，这就是瓶颈所在。
有序向量的概念
上一页我们看到，无序向量出队要遍历找最值，O(n) 是它的瓶颈。一个自然的想法是：干脆让元素一开始就按优先级排好——这就是有序向量的核心思路。
第一名永远在最前/最后，对应极值元素固定在端点
有序向量的入队操作
有序向量的入队，核心难点在于既要找对位置，又要给新元素让路。
有序向量的出队操作
出队只需定位末尾、取值、弹出三步，全程 O(1)。
无序向量 vs 有序向量
「无序」与「有序」看似只是排列差异，但入队与出队的复杂度恰好此消彼长——这是两种向量实现最关键的分水岭。
- 入队 O(1)：直接追加到表尾
- 出队 O(n)：遍历全表寻找极值
- 适合入队远多于出队的场景
- 入队 O(n)：需移动元素腾出位置
- 出队 O(1)：直接取表首或表尾
- 适合出队远多于入队的场景
BBST的基本概念
有序向量查找快，但插入要搬动大量元素，O(n) 的代价让人头疼。有没有一种结构，既能像二分查找一样快定位，又不用为新元素挪位置？平衡二叉搜索树就是答案。
跷跷板两端高度差要受控；对应BBST左右子树高度差不能超限
BBST的结构与优先级队列的映射
元素入队后映射为BBST节点，中序遍历即得有序出队序列
BBST的入队操作
BBST入队 = BST插入 + 失衡修复，每一步都为维护对数级复杂度。
BBST的出队操作
从BBST中取出最大或最小节点，需要四步配合。
三种实现的性能总览
从优先级队列出发，三条分支对应三种实现的入队与出队复杂度。
实现选择的原则
前页列了三种实现在各操作上的复杂度差异，但这只能告诉你『它们各自多快』，不能告诉你『该选谁』。选择不是查表，而是看清这队列的用途。
看距离、负重、时效综合决定，对应看操作、规模、附加需求
基本实现要点回顾
- ✓数据结构没有「谁最强」，只有「谁最贴你场景」
- ✓选之前先问：插入与删除，哪个更常发生
- ✓BBST 看似两全，是把成本塞进了平衡维护里
- ✓复杂度是底线，但代码简洁度同样值得权衡
课后思考
三个开放性问题引导深入琢磨