优先队列C这个话题我确实想好好写一篇。做了这么多年实际项目和算法实现我一直觉得 STL 里最被低估的容器之一就是std::priority_queue。很多人对vector、map、sort熟得不能再熟但一提到“动态取最大值/最小值”的需求第一反应往往是开个临时数组扫一遍或者每次都重新排序。真正把调度、Top-K、最短路径这类代码写几轮之后你就会发现优先队列的出现频率一点都不比map低。这篇文章我不想讲空泛概念直接拆解构造方式、比较器怎么写、常见场景怎么落地以及我踩过的几个坑。不管你是刚玩明白基础 STL、想写出更高效代码的新手还是准备面试刷题、想把底层原理搞清楚的人应该都能从里面找到点东西。1. 优先队列到底在解决什么问题1.1 不是“排序”的替代品是“动态取极值”的利器很多人在理解priority_queue时会下意识把它当成一个“自动排序的容器”这个理解不能说错但会带你走偏。它真正要解决的问题是在一个不断变化的集合里随时拿到当前的最大值或最小值并且要求做的插入、删除、取极值的操作都足够快。举个例子你正在做一个任务调度模块里面不断有任务插入又不断有任务被执行完。如果每次有任务插入都重新排序一遍或者每次取任务都线性扫描全表数据量小的时候看不出来数据量一旦到了几万、几十万性能就会肉眼可见地崩。优先队列的意义在于它把插入和删除的复杂度控制在O(log n)取极值O(1)内存也只要O(n)。你完全不需要时刻维护一个全序数组只需要每时每刻知道“谁最大”或“谁最小”剩下的不用管。还有一种情况是“流式”问题数据一个接一个地来你不能等全部收齐再统一排序。比如实时日志里要监控当前延迟最高的请求或者在线比赛中要动态维护当前分数最高的玩家。这个时候priority_queue就是那种“即插即用”的数据结构。简单说它适合的是持续有 push 和 pop、并且在任意时刻都要查看极值的场景。1.2 典型场景一览调度、Top-K、多路归并、最短路径我个人的经验是不要把优先队列当成一个算法题的“知识点”去死记它更像个基础工具散落在各个地方。常见的场景我随手都能列出一堆任务调度按优先级处理任务同优先级再按时间戳或其他策略执行。Top-K 问题从海量数据里取最大的 K 个或者最小的 K 个不需要全量排序。合并 K 个有序序列多路归并时每次从多个队列头部选最小的元素输出。Dijkstra 最短路径每次寻找距离起点最近的未处理节点。霍夫曼编码从节点集合里反复取权重最小的两个节点合并。事件模拟离散事件系统里按时间顺序处理将来发生的事件。你会发现这些场景有一个共同点它们都需要“动态极值”而不是“完整的全序列”。如果你试图用排序来解决通常也不是不行但会付出多余的开销而且当集合内容持续变化时全量排序的维护成本会非常难受。优先队列的哲学就是只维护你需要的那个极值位置别把整条路都铺平。1.3 数组扫描、排序和堆的复杂度对比我经常用一张小表格给新同事讲清楚为什么优先队列这件事成立。假设集合大小为n我们反复插入m个元素并且频繁取极值做法单次插入单次取极值单次删除极值大致评价数组线性扫描O(1)O(n)O(n)取极值成本太高每次插入后排序O(n log n)O(1)O(1)重复排序太浪费优先队列堆O(log n)O(1)O(log n)各项成本均衡这组对比能看出来优先队列本质上是个“平均主义”方案。它不像扫描那样插入便宜、取极值贵也不像排序那样插入贵、取极值便宜而是把主要的操作都压到了对数级别。对数增长有多慢相信写过一段代码的人都有体会n到一百万的时候log n也就二十左右。这才是它在实际工程里被广泛使用的原因。2. 基本操作与构造细节2.1 默认最大堆与常用 APIC 里std::priority_queue在头文件queue中。默认不写模板参数时它是最小堆还是最大堆很多人第一眼会猜错默认对应的是“最大堆”也就是top()返回当前集合里最大的元素。原因后面讲比较器语义时会解释这里先记住结论就好。#include iostream #include queue int main() { std::priority_queueint pq; pq.push(4); pq.push(10); pq.push(3); pq.push(7); std::cout pq.top() \n; // 输出 10 pq.pop(); // 删除最大元素 10 std::cout pq.top() \n; // 输出 7 std::cout pq.size() \n; // 输出 3 return 0; }它的接口非常精简push插入元素pop弹出顶部元素top返回顶部元素empty判断是否为空size返回元素数量还有一个swap用于交换两个队列。没有begin/end没有迭代器也不允许你直接遍历。这不是 API 缺陷而是设计意图它只保证极值访问不承诺内部完全有序。如果你需要有序输出全部元素可以不断pop直到空这样出来的序列一定是有序的。如果直接去拿底层的容器对象瞎遍历就不要指望它有任何顺序规律了。2.2 如何用一个已有 vector 初始化有时候你手里已经有一个vector希望直接把它构造成优先队列。最自然的方法可能是一次次 push但那样复杂度是O(n log n)效率上略微浪费。实际上std::priority_queue支持从一个现有容器构造内部会直接调用堆化算法make_heap复杂度是O(n)省掉不少重复上浮操作。#include queue #include vector int main() { std::vectorint data {3, 1, 4, 1, 5, 9, 2, 6}; // 用现有容器构造内部会做 make_heap std::priority_queueint pq(std::lessint(), std::move(data)); std::cout pq.top() \n; // 输出 9 return 0; }注意这里我把data用std::move移动进去了避免一次不必要的复制。如果你还想继续使用原来的vector就不要加move但代价是复制整个数据。对于大量元素这个复制成本不能忽略。工程里常见的毛病就是构造时用了拷贝导致原本期望的O(n)堆化硬生生带上一个大常数数据量一大就肉疼。2.3 底层容器与复杂度std::priority_queue本身其实不是一个崭新的数据结构它是一个容器适配器底层默认使用std::vector在上面调用堆相关的算法。模板签名可怕归可怕其实就是三件事template class T, class Container std::vectorT, class Compare std::lesstypename Container::value_type class priority_queue;第一个参数是元素类型第二个是底层容器第三个是比较器。默认容器是vector也可以换成deque但换的意义不大因为vector的内存局部性和随机访问特性最适合堆算法。复杂度方面top()是O(1)push和pop都是O(log n)从容器构造是O(n)。这些数据都很透明没有太多弯弯绕绕真正容易出问题的是比较器。3. 自定义比较器真正决定优先级的那一行代码3.1 最小堆与 std::greater默认最大堆是std::lessint作为比较器。如果你想要最小堆最简单的办法是把比较器换成std::greaterint。#include queue #include vector #include functional int main() { std::priority_queueint, std::vectorint, std::greaterint pq; pq.push(4); pq.push(10); pq.push(3); pq.push(7); std::cout pq.top() \n; // 输出 3 return 0; }这里就引出了 C 优先队列最绕的一点比较器的方向和你直觉里的“谁优先级高”是反着来的。std::priority_queue的第三个模板参数Compare表示的是“谁的优先级更低”。当Compare(a, b)返回true时意味着a排在b的后面也就是a的优先级更低。std::lessint返回a b它会在a更小时让a优先级更低于是“更大”的元素反而跑到堆顶形成最大堆。同理std::greaterint返回a b它让“更大”的元素优先级更低于是最小元素在堆顶形成最小堆。这句话我建议初学者抄在本子上因为几乎所有自定义比较器的错误都源于这里。3.2 函数对象和 lambda实际开发里比较逻辑往往不是简单的int大小而是对象里某个字段大小的综合判断。C 允许传入一个函数对象或者 lambda。lambda 写法很直观我用得最多#include queue #include vector struct Node { int id; int dist; }; int main() { auto cmp [](const Node a, const Node b) { // dist 小的优先所以 return true 时表示 a 的优先级更低 return a.dist b.dist; }; std::priority_queueNode, std::vectorNode, decltype(cmp) pq(cmp); pq.push({1, 100}); pq.push({2, 50}); pq.push({3, 200}); std::cout pq.top().id \n; // 输出 2因为 dist50 最小 return 0; }这里decltype(cmp)是 lambda 的类型构造pq时必须把cmp传进去否则它不知道这个 lambda 是谁。如果不需要捕获任何外部变量在 C20 之前 lambda 的默认构造也有一定限制所以每次构造时传一次cmp最保险。还有一个细节是比较器返回值是bool但实现里很依赖“严格弱序”也就是对于任意两个元素a和bcmp(a,b)和cmp(b,a)不能同时为真而且在元素相等时两个比较都必须返回false。这一点快到踩坑部分再展开。3.3 给自定义类型定义优先级如果某个自定义类型在很多地方都要放进优先队列重载operator是更省事的方案因为默认比较器就是std::less它会调用operator。不过这里要格外小心因为operator返回true表示的依然是“谁的优先级低”。我希望“优先级数字大的先执行”就得把“优先级更大”放到比较关系的“更大”一侧。#include queue #include string struct Job { int priority; int create_time; std::string name; // 默认 priority_queue 用它做最大堆优先级数字大的先出队 bool operator(const Job other) const { if (priority ! other.priority) { return priority other.priority; } // 同优先级下创建时间晚的视为更紧急靠后调用 operator return create_time other.create_time; } }; int main() { std::priority_queueJob pq; pq.push({1, 100, A}); pq.push({9, 200, B}); pq.push({5, 150, C}); std::cout pq.top().name \n; // 输出 B return 0; }这段代码里B的优先级数字最大所以它最先出队。同优先级的时候创建时间更晚的任务反而更急我在operator里写成create_time other.create_time让晚创建的对象“更晚”比较、优先级更高。这个逻辑写成自然语言有点绕但代码里非常清晰比较器只是在定义“谁应该排在后面”排在后面的元素会优先浮到堆顶。3.4 比较器语义的三个判断节点我习惯在写自定义比较器前先问自己三个问题我想让哪种元素最先出队如果两个元素的优先级一样比较器应该返回什么比较器会不会因为对象内部字段变化而产生不同的结果第一个问题决定了整个比较器方向。第二个问题看似简单但很多人会写成return a b或者return a b这就不满足严格弱序极端情况下会让堆内部结构错乱。第三个问题很隐蔽如果比较器依赖一个可变字段而该字段在元素入队后又被改动了堆的性质就可能被破坏。后面踩坑部分我会专门讲这个。4. 经典场景实操Top-K、多路归并与惰性删除4.1 从 N 个数里高效挑出 Top-KTop-K 是优先队列最经典的应用之一。比如你有一万个数字要找出最大的五个。直觉做法是先排序再取前五个复杂度O(n log n)。用最小堆做复杂度可以降到O(n log k)当k远小于n时优势非常明显。思路是维护一个容量为k的最小堆堆里存当前见过的最大的k个数。如果新来的数字比堆顶大说明堆顶不在 Top-K 范围里把它替换掉。#include queue #include vector std::vectorint findTopK(const std::vectorint nums, int k) { if (k 0) return {}; std::priority_queueint, std::vectorint, std::greaterint minHeap; for (int x : nums) { if ((int)minHeap.size() k) { minHeap.push(x); } else if (x minHeap.top()) { minHeap.pop(); minHeap.push(x); } } std::vectorint result; while (!minHeap.empty()) { result.push_back(minHeap.top()); minHeap.pop(); } return result; }代码里我用的是最小堆堆顶是当前 Top-K 里最小的那个。每来一个新元素只要它比堆顶大就说明堆顶已经危险了把它挤出去。这么做有个隐藏好处数据是流式的不需要一次性全部加载到内存。如果你处理的是“最大的 K 个”逻辑正好反过来用一个容量为k的最大堆。4.2 合并 K 个有序序列另一个高频场景是合并多个有序序列。一个形象的例子是外部排序中把多个已经排好序的小文件合并成一个大的有序文件。朴素做法是每轮把k个序列的头部元素都拿出来比较取最小的一个输出复杂度很高。用最小堆可以做到先把每个序列的头节点放入堆每次弹出堆顶这个堆顶就是当前全局最小然后把这个序列的下一个元素补进去。#include queue #include vector struct Item { int value; int row; int col; // 最小堆value 小的优先 bool operator(const Item other) const { return value other.value; } }; std::vectorint mergeSortedArrays(const std::vectorstd::vectorint arrays) { std::priority_queueItem pq; for (int i 0; i (int)arrays.size(); i) { if (!arrays[i].empty()) { pq.push({arrays[i][0], i, 0}); } } std::vectorint result; while (!pq.empty()) { Item cur pq.top(); pq.pop(); result.push_back(cur.value); if (cur.col 1 (int)arrays[cur.row].size()) { pq.push({arrays[cur.row][cur.col 1], cur.row, cur.col 1}); } } return result; }这里Item的operator返回value other.value所以越小的value越先出队。整体复杂度是O(n log k)其中n是所有序列总元素数k是序列条数。这个思路在数据库归并、日志归并、外部排序里都是标配不是算法题专属。4.3 Dijkstra 场景惰性删除Dijkstra 最短路径几乎可以算优先队列的“灵魂应用”。但直接实现时会发现一个问题优先队列只能改“队头”不能改“中间某个元素”。而最短路径算法在更新到更短距离时理论上需要修改队列里对应节点的优先级。C 的std::priority_queue没有提供 decrease-key 操作常规做法就是“惰性删除”每次更新距离不删除旧状态直接 push 一个新的状态等到弹出旧状态时发现它已经过期直接忽略。#include queue #include vector struct State { int node; long long distance; // 距离小的优先 bool operator(const State other) const { return distance other.distance; } }; std::vectorlong long dijkstra(int start, const std::vectorstd::vectorstd::pairint, long long graph) { const long long INF 4e18; std::vectorlong long dist(graph.size(), INF); std::priority_queueState pq; dist[start] 0; pq.push({start, 0}); while (!pq.empty()) { State cur pq.top(); pq.pop(); if (cur.distance ! dist[cur.node]) { continue; // 这是一个过期状态直接忽略 } for (auto edge : graph[cur.node]) { int v edge.first; long long w edge.second; if (dist[v] dist[cur.node] w) { dist[v] dist[cur.node] w; pq.push({v, dist[v]}); } } } return dist; }关键就是if (cur.distance ! dist[cur.node]) continue;这一行过滤掉所有没用的历史记录。这种写法的好处是简单直接缺点是堆里会同时存在同一节点的多个状态内存占用量可能比理论值高。但在绝大多数实际数据上这个方案已经够快而且代码风险远低于自己实现索引堆。4.4 不止算法题调度系统的思路其实一样写调度逻辑的时候优先队列的思路也极其相似。我做过一个简化版的任务调度器任务对象包含优先级、创建时间、预计执行时长。最朴素的实现是每来一个任务就把任务塞进列表然后每次取任务时线性扫描找最高优先级结果任务一多就卡。后来改成优先队列每次执行前top()看谁最紧急执行完pop()再插入新任务几十万条任务跑起来基本毫无压力。核心教训是凡是“动态集合里反复取极值”的逻辑优先队列都值得优先考虑。5. 踩坑实录priority_queue 的常见问题5.1 搞反比较器方向这个坑我见得太多了而且几乎每个写自定义比较器的人都踩过。拿最小堆举例很多人会觉得“我要最小堆那比较器就应该返回谁更小于是写a b”结果发现堆顶是最大的瞬间怀疑人生。前面已经讲过priority_queue的比较器返回true表示“第一个参数的优先级更低”跟直觉正好相反。所以我建议每次写完比较器用三个不同数据先跑一下快速验证堆顶是不是你想要的值。用{1, 9, 5}这种边界明显的用例一测方向对不对立刻见分晓。5.2 比较器破坏了严格弱序严格弱序是个听起来很玄的词翻译成人话就是比较关系要自洽、不矛盾。一个最常见的坏例子是auto bad_cmp [](int a, int b) { return a b; // 相等时也返回 true };当a b时bad_cmp(a, b)和bad_cmp(b, a)同时返回true这就彻底破坏了堆结构。用这种比较器的后果不一定每次都能稳定复现但可能在数据量一大或者结构稍微复杂时突然给你一个错误的输出。正确的做法是相等时必须返回false比如写成a b、a b或者a.dist b.dist这类严格版本。5.3 队列元素已经“过期”这个问题在 Dijkstra、A*、动态规划转移里特别常见。节点状态被更新后旧状态还留在堆里如果不做过滤弹出的可能是一个早就失效的旧值。解决方式就是惰性删除在同一节点上保留一个“最新可信值”如果弹出的状态与最新可信值不一致就跳过。很多人第一次写 Dijkstra 时没加这一行结果处理出奇怪的最短路径各种怀疑人生。加一行if (cur.distance ! dist[cur.node]) continue;世界立刻安静。5.4 队列里的元素被“偷偷修改”优先队列假设堆内元素在入队后不会被外部修改。如果你通过某种方式拿到一个对象引用然后改了对象内部的字段这个对象在堆里的位置不会自动更新堆的性质就被破坏了。比如你有这样一个结构体struct Task { int priority; std::string name; };入队后你把某个Task的priority改小了但这个对象还留在堆里旧位置上后续的top()可能给出错误结果。意识到这一点后解决办法有两个要么不保存原始引用每次更新都按新状态重新push并忽略旧状态要么改用支持 decrease-key 的索引堆主动移动元素位置。工程上惰性删除往往更实用因为它代码量小、容易理解。5.5 性能陷阱复制开销与容器预留如果队列里存放的是很大的自定义对象push和pop过程会发生拷贝或移动频繁操作时性能可能成为瓶颈。尤其当你把对象设计得很胖还塞了好几个std::string和容器堆调整时的复制开销会放大。一般建议优先队列里存储轻量对象比如只存id然后通过全局数组或unordered_map去查具体信息或者存指针、智能指针。如果你确实需要存对象至少保证类型有高效的移动构造函数。还有一个冷门细节如果你手里已经有一个vector要建堆用构造函数传入std::move(data)是O(n)堆化比反复push的O(n log n)明显更快算是免费的小优化。6. 标准库不够用时自己写一个6.1 一个最简最小堆实现虽然std::priority_queue能覆盖绝大多数需求但当你需要“修改堆中某个元素的优先级”或“删除堆中某个指定元素”时标准库适配器就力不从心了。自己实现一个二叉堆并不难核心就是上浮sift_up和下沉sift_down。下面这个是自己常用的一套极简最小堆骨架#include vector #include algorithm template typename T class MinHeap { public: bool empty() const { return heap.empty(); } size_t size() const { return heap.size(); } void push(const T val) { heap.push_back(val); siftUp((int)heap.size() - 1); } T pop() { T ret heap.front(); std::swap(heap.front(), heap.back()); heap.pop_back(); if (!heap.empty()) siftDown(0); return ret; } const T top() const { return heap.front(); } private: void siftUp(int idx) { while (idx 0) { int parent (idx - 1) / 2; if (heap[idx] heap[parent]) { std::swap(heap[idx], heap[parent]); idx parent; } else { break; } } } void siftDown(int idx) { int n (int)heap.size(); while (true) { int left idx * 2 1; int right idx * 2 2; int minimum idx; if (left n heap[left] heap[minimum]) minimum left; if (right n heap[right] heap[minimum]) minimum right; if (minimum idx) break; std::swap(heap[idx], heap[minimum]); idx minimum; } } std::vectorT heap; };这里我直接用operator来定义大小想要最小堆就把小于号当“更优先”的意思。如果你要最大堆把两份比较里的换成即可。这个实现虽然简单但 push、pop、top 的复杂度跟标准库一致。平常不需要动标准库但如果公司项目里需要自己控制内存池、或者要嵌入某个不能依赖 STL 的环境这种极简版本改起来非常方便。6.2 支持更新和删除的索引堆当你不仅要取最小值还要随时修改某个元素的优先级、或者删除某个中间元素时普通堆就不够用了。这时需要用“索引堆”堆里不直接存对象而是存元素下标再用一个pos数组记录每个元素当前在堆里的位置。当某个元素优先级更新后你通过pos找到它在堆里的下标直接在那个位置做上浮或下沉即可。这个操作就是 Dijkstra 里常说的 decrease-key 的核心。手写索引堆比普通堆复杂但只要写过一次之后再遇到动态优先级的问题你会非常感激这个结构。我的建议是日常顺手备一个极简普通堆当模板真需要索引堆的时候再往上面加pos映射和更新方法。回到工具本身std::priority_queue不是为了炫技也不是算法题里才能碰到的“考试容器”。它是那种看一眼觉得简单、实际用起来有讲究、用好了会很顺手的工具。比较器方向记不清没关系多跑几组测试就能验证碰到需要动态改优先级的场景先想着惰性删除等数据规模真的到了撑不住的程度再自己去实现索引堆也不迟。我自己每次写调度或者图论相关的代码都会先想清楚一件事我要的是“全序”还是“极值”如果是后者优先队列就是第一选择。