Skip to main content

Chapter 24: Priority Queue

核心问题与阅读主线

本章导读6 个核心小节 · 附自检与总结

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_queueset / 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。

核心判断

  1. 核心路径仅需 push、top、pop,且重视紧凑内存与缓存局部性:选 priority_queue。
  2. 主路径围绕最值推进,偶发取消或改优先级:选 priority_queue + 状态/版本表懒惰删除。
  3. 必须支持 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>;

排查顺序

  1. 操作模型:确认业务是否仅围绕当前最值推进。
  2. 比较语义:确认比较器方向与“弱序靠后即堆顶”一致,并显式写入 tie-breaker。
  3. 键可变性:确认优先级入队后是否变化,必要时采用版本号懒惰删除。
  4. 索引需求:确认取消、查找或遍历是否需额外状态表,或直接换用 set。
  5. 容器代价:确认扩容与堆调整带来的引用失效及元素移动开销可接受。

最小自检任务​

动手自检先独立判断

阅读下面代码,判断三次输出的任务名,并说明每次 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) 最小堆维护。