Chapter 24: Priority Queue
核心问题与阅读主线
std::priority_queue 解决持续入队、反复只取当前最高优先级元素的调度需求,把底层容器、堆维护算法与比较器封装成受限队列接口。工程实践中最容易踩坑的两点在于:比较器方向与排序直觉相反,且适配器刻意屏蔽了定位查找、遍历与原地修改优先级的能力。
全章共用代码样本(下文各节持续拆解)
贯穿本章的最小材料是一组待执行任务(priority 大者优先;同优先级时 sequence 小者先执行),其中的比较器方向是全章最容易写反的位置:
#include <queue>
#include <string>
#include <vector>
struct Task {
int priority;
int sequence;
std::string name;
};
struct TaskOrder {
bool operator()(const Task& lhs, const Task& rhs) const {
if (lhs.priority != rhs.priority) {
return lhs.priority < rhs.priority;
}
return lhs.sequence > rhs.sequence;
}
};
using ReadyQueue = std::priority_queue<Task, std::vector<Task>, TaskOrder>;
TaskOrder 返回 true 表示 lhs 在严格弱序中排在 rhs 前面,而 top() 返回排在最后的元素;因此 priority 最大、同优先级下 sequence 最小的 Task 会浮到堆顶。
24.1 heap-backed adaptor model
std::priority_queue 对外只暴露受限队列接口(push、emplace、pop、top、empty、size),内部结构是随机访问区间上的二叉堆。C++ working draft 的 priority_queue 条目通过受保护成员 c(底层容器)与 comp(比较器),以 c.front()、c.push_back()、c.pop_back() 配合 make_heap、push_heap、pop_heap 描述其成员语义:
| 接口层动作 | 底层容器与堆算法动作 | 堆不变量结果 |
|---|---|---|
top() | 读取 c.front() | 不改变堆 |
push(x) | c.push_back(x) 后调用 push_heap | 新元素上浮入堆 |
emplace(args...) | c.emplace_back(args...) 后调用 push_heap | 原地构造后上浮入堆 |
pop() | 调用 pop_heap 后 c.pop_back() | 原堆顶移至末尾并移除 |
| 构造自区间 | 初始化 c 后调用 make_heap | 整个区间成堆 |
关键事实
二叉堆以数组下标表达树形关系:位置 i 的父节点为 (i - 1) / 2,左右孩子为 2 * i + 1 与 2 * i + 2,因此底层必须支持随机访问迭代器。合法堆不变量要求任意非根位置 i 均满足 comp(parent, child) == false——默认 std::less<T> 使 parent < child 为 false(父节点不小于孩子,堆顶最大),改用 std::greater<T> 使 parent > child 为 false(父节点不大于孩子,堆顶最小)。
阅读标准库实现时,顺着模板参数(T、Container、Compare)找到 c 与 comp,即可把成员操作直接映射到 make_heap、push_heap、pop_heap。这一封装收窄了接口:不提供迭代器、键查找和任意位置删除;只要父子关系满足堆不变量,即使 ReadyQueue 底层数组看似未全序排序,堆顶依然严格正确。
24.2 vector 底层容器与 comparator
底层容器必须同时满足 heap 算法与适配器接口,提供随机访问迭代器及 front()、push_back()、pop_back():
| 底层容器 | 接口满足度 | 内存局部性与适用场景 |
|---|---|---|
std::vector<T>(默认) | 满足随机访问与尾部操作 | 连续存储、缓存局部性最佳;扩容会触发整体搬移 |
std::deque<T> | 满足随机访问与尾部操作 | 分段连续、无需整体重分配,适合大对象或忌扩容尖刺场景 |
std::list<T> | 缺随机访问迭代器(不可用) | 节点式结构无法通过下标计算 (i - 1) / 2 |
比较器 Compare 需满足严格弱序(strict weak ordering):comp(a, b) == true 表示 a 排在 b 前面,而 top() 返回排在最后的元素。因此默认 std::less<T> 构成最大堆,std::greater<T> 构成最小堆:
#include <functional>
#include <iostream>
#include <queue>
#include <vector>
int main() {
std::priority_queue<int> max_heap;
std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;
for (int value : {4, 1, 7, 3}) {
max_heap.push(value);
min_heap.push(value);
}
std::cout << max_heap.top() << '\n'; // 7
std::cout << min_heap.top() << '\n'; // 1
}
TaskOrder 按同一规则工作:先用 lhs.priority < rhs.priority 让大优先级浮向堆顶,同优先级时用 lhs.sequence > rhs.sequence 把更小的 sequence 推向弱序末尾,从而将“同优先级先进先出”显式编码进元素,不依赖容器记忆插入顺序。
边界与误区
- 有状态比较器风险:若
comp读取外部优先级表且表内容更新,队列不会自动重建堆;稳妥做法是将比较键存入元素,或在变更后重新插入、重建堆,或改用可定位更新的容器。 - 副作用破坏弱序:heap 算法每次调整会沿树高多次调用
comp,比较器必须无副作用且结果稳定,若修改元素或依赖时间等易变状态,会损坏堆结构。
24.3 push、pop 与 top 的堆状态路径
push 的状态路径分两阶段:先由底层容器 push_back 追加到末尾(默认 std::vector 扩容会移动已有元素),再由 push_heap 沿父链上浮。在下面的 ReadyQueue 插入序列中,插入 render 时 TaskOrder(parse, render) 为 true,render 上浮为根;再插入 write 时因其优先级低于根而留在下层,最终 top() 返回 render:
ReadyQueue ready;
ready.push(Task{5, 0, "parse"});
ready.push(Task{9, 1, "render"});
ready.push(Task{5, 2, "write"});
std::cout << ready.top().name << '\n'; // render
top() 为常数时间操作,返回 const_reference 以阻止调用方直接修改堆顶关键字段而破坏父子不变量。pop() 同样分两阶段:先调用 pop_heap 将堆顶换到末尾并修复剩余堆,再由 c.pop_back() 移除末尾元素——因此 pop() 返回 void,消费堆顶时必须先复制或移动再弹出,并在下一次读取前重新调用 top():
while (!ready.empty()) {
Task task = ready.top();
ready.pop();
std::cout << task.name << '\n';
}
边界与误区
- 引用立即失效:
priority_queue虽不暴露迭代器,但只要发生push或pop,旧top()引用(及派生类或调试接口拿到底层容器的引用/迭代器)均可能因vector扩容或堆调整覆写元素而失效,操作后必须重新获取。 - 分段异常安全:
push_back阶段的内存分配/对象构造与 heap 调整阶段的比较/移动分属不同提交点;应使比较器廉价且不抛异常、元素移动成本可预测,审阅实现时需核查异常传播后的容器长度与堆状态承诺。
24.4 make_heap、push_heap、pop_heap 与堆调整
make_heap、push_heap 与 pop_heap 是直接作用于随机访问区间的底层算法(参见 C++ working draft 的 heap operations):
| 算法 | 前置条件 | 核心动作与复杂度上界 |
|---|---|---|
make_heap(first, last, comp) | 任意随机访问区间 [first, last) | 原地建堆,至多 3N 次比较(线性时间,适合批量初始化) |
push_heap(first, last, comp) | [first, last - 1) 已成堆 | 将 last - 1 沿父链上浮,比较次数 O(log N) |
pop_heap(first, last, comp) | [first, last) 为非空堆 | 交换根与 last - 1 并下沉修复 [first, last - 1),比较次数 O(log N) |
下面简化的 teaching_sift_up 展示了 push_heap 仅沿父链上浮的核心路径:
template<class T, class Compare>
void teaching_sift_up(std::vector<T>& data, std::size_t child, Compare comp) {
T value = std::move(data[child]);
while (child > 0) {
std::size_t parent = (child - 1) / 2;
if (!comp(data[parent], value)) {
break;
}
data[child] = std::move(data[parent]);
child = parent;
}
data[child] = std::move(value);
}
当 comp(data[parent], value) 为 true(默认最大堆即 data[parent] < value)时,父节点下移、新值继续上浮;一旦条件为 false,当前位置即满足堆不变量。对称地,pop_heap 交换根与 last - 1 后执行下沉:每步只需比较当前节点的两个孩子与候选值,将更高优先级的孩子上移,开销同样受树高限制。
边界与误区
push_heap不追加元素:直接调用<algorithm>中的push_heap时,新元素必须已提前放入last - 1。pop_heap不缩短容器:pop_heap仅把原堆顶换到末尾并修复前段区间,调用方必须紧接pop_back()才算完成删除。
priority_queue 的工程价值正在于将“容器尺寸变更”与“堆区间边界”绑定在一起,避免调用方手工维护时破坏堆区间。
24.5 与 set 的区别和选型边界
priority_queue 仅维护当前极值,而 set / multiset 维护全局有序键空间,二者的操作模型与内存代价差异显著:
| 维度 | priority_queue | set / multiset |
|---|---|---|
| 底层模型 | 随机访问区间上的二叉堆 | 节点式有序树(通常为红黑树) |
| 核心目标 | 快速读取并弹出当前最值 | 维护全局有序键空间 |
| 最值读取 | top() 常数时间 | begin() / rbegin() 常数时间 |
| 插入 | push 对数时间(尾部追加 + 上浮) | insert 对数时间(树路径插入与平衡) |
| 删除当前最值 | pop 对数时间 | 摊销常数到对数时间(erase(begin()) / erase(prev(end()))) |
| 删除任意元素 | 无直接接口 | 支持按迭代器或键删除 |
| 查找指定键 | 无直接接口 | 支持 find、lower_bound、upper_bound |
| 顺序遍历 | 无迭代器接口 | 支持双向有序遍历 |
| 同优先级处理 | 需将 tie-breaker 显式编入元素 | 由键关系决定,multiset 允许等价键 |
| 位置稳定性 | 堆调整或扩容会移动元素 | 节点式结构通常保持其他迭代器稳定 |
结构差异决定了缓存与功能的取舍:set 每个元素需单独分配节点并保存平衡状态及左右父指针,缓存局部性通常弱于 vector 承载的连续堆;而 priority_queue 则以收窄接口为代价换取紧凑内存。若仅偶发需要取消或更新优先级(标准库未提供 decrease-key / increase-key),通常用辅助表配合懒惰删除(lazy deletion)即可补齐:
- 任务取消:维护
ID -> 状态哈希表,pop()时跳过已取消条目。 - 优先级更新:压入携带新版本号或新距离的副本,弹出时核对当前版本或记录表(如 Dijkstra 常见实现);若原地更新频繁,则改用可定位更新的索引堆或
set。
核心判断
- 核心路径仅需
push、top、pop,且重视紧凑内存与缓存局部性:选priority_queue。 - 主路径围绕最值推进,偶发取消或改优先级:选
priority_queue+ 状态/版本表懒惰删除。 - 必须支持
find、erase(key)、lower_bound、有序遍历或稳定节点引用:选set/multiset或“堆 + 位置索引”复合结构。
24.6 工程使用场景
在任务调度、线程池、离散事件模拟与消息处理中,每次只需取当前最高优先级条目执行,使用 priority_queue 维持对数级入出堆远比全量排序高效。
延迟任务队列
以到期时间戳为优先级建立最小堆,top() 即最早到期任务;未到期时调度器等待差值即可,若需支持取消则配合任务 ID 状态表在弹出时过滤无效条目:
struct TimerTask {
long long due_time_ms;
int id;
};
struct EarlierDueTime {
bool operator()(const TimerTask& lhs, const TimerTask& rhs) const {
return lhs.due_time_ms > rhs.due_time_ms;
}
};
using TimerQueue = std::priority_queue<TimerTask, std::vector<TimerTask>, EarlierDueTime>;
EarlierDueTime 通过 lhs.due_time_ms > rhs.due_time_ms 让较早到期的任务留在堆顶。
数据流 Top-K
在海量输入中保留最大的 K 个元素,可维护大小上限为 K 的最小堆——堆顶是当前候选中的最小值,新值更大时弹出堆顶再入堆,空间为 O(K),单次有效替换成本为 O(log K):
#include <functional>
#include <queue>
#include <vector>
std::vector<int> top_k_largest(const std::vector<int>& input, std::size_t k) {
std::priority_queue<int, std::vector<int>, std::greater<int>> heap;
for (int value : input) {
if (heap.size() < k) {
heap.push(value);
} else if (k != 0 && value > heap.top()) {
heap.pop();
heap.push(value);
}
}
std::vector<int> result;
while (!heap.empty()) {
result.push_back(heap.top());
heap.pop();
}
return result;
}
返回的 result 仅保证包含最大的 K 个元素,不保证输出有序;若需有序结果,可在收集后排序或逆序写入。
Dijkstra 最短路(懒惰删除)
针对标准 priority_queue 缺少 decrease-key 接口的边界,工程上常将更短的新距离直接压入最小堆 Frontier,并在弹出时比对 state.distance 与 dist[state.vertex],不一致则跳过过期状态:
struct State {
int distance;
int vertex;
};
struct ShorterDistance {
bool operator()(const State& lhs, const State& rhs) const {
return lhs.distance > rhs.distance;
}
};
using Frontier = std::priority_queue<State, std::vector<State>, ShorterDistance>;
排查顺序
- 操作模型:确认业务是否仅围绕当前最值推进。
- 比较语义:确认比较器方向与“弱序靠后即堆顶”一致,并显式写入 tie-breaker。
- 键可变性:确认优先级入队后是否变化,必要时采用版本号懒惰删除。
- 索引需求:确认取消、查找或遍历是否需额外状态表,或直接换用
set。 - 容器代价:确认扩容与堆调整带来的引用失效及元素移动开销可接受。
最小自检任务
阅读下面代码,判断三次输出的任务名,并说明每次 push / pop 后队列内部需要维护什么不变量。
ReadyQueue ready;
ready.push(Task{3, 0, "tokenize"});
ready.push(Task{7, 1, "compile"});
ready.push(Task{7, 2, "link"});
ready.push(Task{5, 3, "package"});
std::cout << ready.top().name << '\n';
ready.pop();
std::cout << ready.top().name << '\n';
ready.pop();
std::cout << ready.top().name << '\n';
本章知识点总结
- 适配器模型
std::priority_queue用受限队列接口封装底层随机访问容器c与比较器comp,通过make_heap、push_heap、pop_heap维护二叉堆。 - 堆不变量与底层容器
非根位置均满足
comp(parent, child) == false,底层容器须提供随机访问迭代器及front()、push_back()、pop_back()(std::vector、std::deque可用,std::list不可用)。 - 比较器方向与约束
comp(a, b) == true表示a排在b前面而top()返回最后元素(默认std::less<T>为最大堆,std::greater<T>为最小堆);比较器须满足严格弱序、无副作用且不依赖外部可变状态。 - 状态路径与失效边界
push先追加再push_heap上浮,pop先pop_heap换位修复再pop_back()删除(返回void);top()返回const_reference,任意push/pop后旧引用均应视为失效。 - Heap 算法分工
make_heap以至多3N次比较完成批量建堆,push_heap与pop_heap仅做对数级堆修复,不改变容器大小。 - 与 set 选型边界
仅围绕最值推进且看重缓存局部性时选
priority_queue;需要find、erase(key)、lower_bound、有序遍历或稳定引用时选set/multiset。 - 无原地更新的对策
标准
priority_queue缺少任意删除与decrease-key,取消与优先级更新(如定时器、Dijkstra)通常用状态/版本表配合懒惰删除处理,Top-K 用固定容量O(K)最小堆维护。