先说我自己的感受priority_queue配pair这件事几乎是每个写 C 图论和算法题的人都会撞上的墙。默认规则能跑一旦要按second排、按权值排、或者做小顶堆立刻一堆编译错误和诡异行为。这篇文章把我这几年在项目里和刷题时踩过的排序相关的坑、用过的三种写法、以及大小顶堆方向混淆的底层逻辑一次性理清楚。1. 问题场景为什么 pair 会频繁出现在 priority_queue 里1.1 默认排序的“意外”与局限std::pair是 C 里最常见的一对一组合容器priority_queue又是自带堆结构的优先级容器两者结合最常见的场景就是——把“节点编号 权值”或者“起始点 终点”打包放进堆里。默认情况下priority_queue直接用std::less来比较元素而std::pair的比较规则是字典序先比first再比second。先看一段最简单的代码#include iostream #include queue #include utility int main() { std::priority_queuestd::pairint, int pq; pq.push({1, 5}); pq.push({2, 4}); pq.push({1, 3}); pq.push({3, 1}); while (!pq.empty()) { auto [a, b] pq.top(); std::cout a b \n; pq.pop(); } return 0; }这段代码输出的顺序是什么是3 1、2 4、1 5、1 3。为什么同样的first 15排在3前面因为pair先比firstfirst相等就比second。也就是说默认规则下大顶堆由first决定first相同再接second。问题就来了在很多实际场景里我只想按second排序或者想实现一个小顶堆。比如 Dijkstra 算法中pairint, int的两个元素分别是“路径长度”和“节点编号”如果first是路径长度默认大顶堆就完全不符合需求因为 Dijkstra 每次要取的是“当前距离最短”的节点需要的是小顶堆而且要按first排序。这时候你就必须自定义排序算法。1.2 自定义排序的核心难点在哪priority_queue的模板签名长这样templateclass T, class Container std::vectorT, class Compare std::lesstypename Container::value_type class priority_queue;三个模板参数分别是元素类型、底层容器、比较器。Compare是一个可调用对象默认用std::less。很多人卡住的第一个点Compare的参数写反了或者 lambda 的写法不知道要传入构造函数。第二个难点就是方向问题。这个我在第 3 节专门讲这里先记住一个结论priority_queue的比较器返回true时表示第一个参数的优先级低于第二个参数也就是它会待在堆的更下方。这个规则和std::sort完全相反超多人在这里翻车。第三个难点是pair本身不是自定义类型你不能给它写成员形式的operator只能通过第三方的比较方式来影响堆的排序。所以接下来要讲的三种方式本质上都是提供一个“外部比较器”。2. 自定义排序的三把刀仿函数、lambda、重载运算符2.1 方法一函数对象仿函数写法函数对象是最经典、兼容性最好的写法。定义一个结构体重载operator()然后把结构体类型作为priority_queue的第三个模板参数。比如我要实现一个“按second从小到大排”的堆也就是second越小越靠顶#include iostream #include queue #include utility #include vector struct CmpBySecond { bool operator()(const std::pairint, int a, const std::pairint, int b) const { return a.second b.second; // 注意这是小顶堆逻辑 } }; int main() { std::priority_queuestd::pairint, int, std::vectorstd::pairint, int, CmpBySecond pq; pq.push({1, 5}); pq.push({2, 4}); pq.push({1, 3}); pq.push({3, 1}); while (!pq.empty()) { auto [a, b] pq.top(); std::cout a b \n; pq.pop(); } return 0; }输出是3 1、1 3、2 4、1 5。如果你想要大顶堆second越大越靠顶就把operator()里的改成bool operator()(const std::pairint, int a, const std::pairint, int b) const { return a.second b.second; // 大顶堆逻辑 }这里有一个非常关键的点如果你直接写return a.second b.second直觉上可能会觉得这是“升序”但在priority_queue里这个比较器会让second小的靠顶也就是小顶堆效果。很多初学者在这里纠结半天我建议直接做试验写两个小例子一个一个记住结果即可。实践经验比死记规则更靠谱。函数对象的优点是可以额外携带状态比如根据某个全局标志位决定比较规则。缺点就是代码量稍微多几行但可读性其实是最好的团队协作时一眼就能看懂意图。2.2 方法二lambda 表达式写法lambda 是写快速原型和刷题时最常用的方式。但必须注意因为 lambda 的闭包类型是匿名的、不可默认构造的所以你不能只把 lambda 类型传给模板参数还必须把 lambda 对象传入构造函数。正确写法#include iostream #include queue #include utility #include vector int main() { auto cmp [](const std::pairint, int a, const std::pairint, int b) { return a.second b.second; // 小顶堆second 小的靠顶 }; std::priority_queuestd::pairint, int, std::vectorstd::pairint, int, decltype(cmp) pq(cmp); // 必须把 cmp 传进去 pq.push({1, 5}); pq.push({2, 4}); pq.push({1, 3}); pq.push({3, 1}); while (!pq.empty()) { auto [a, b] pq.top(); std::cout a b \n; pq.pop(); } return 0; }错误写法只写decltype(cmp)却不传cmp给构造函数这会导致编译错误。因为 lambda 类型没有默认构造函数。这里很多人栽过我当年也栽过编译器的报错信息还特别长容易让人懵。如果 lambda 是空捕获列表[]也就是不捕获任何变量那么实际上它在 C20 之后是可以默认构造的但为了兼容老标准最好的习惯仍然是“无论是否捕获都显式把 lambda 对象传给构造函数”。这样代码在所有启用 C11 以上的环境都能稳定编译。我个人的建议是如果比较逻辑简单lambda 可以如果比较逻辑超过三行或者要在多个地方复用还是用函数对象吧省得每次都要复制粘贴 lambda。2.3 方法三重载 operator让 pair 变成“可排序的节点”第三种方式思路不同不直接给pair写比较器而是把pair包装成一个自定义结构体并重载它的operator。这样一来堆本身根本不需要第三个模板参数用默认的std::less就会自动调用结构体的运算符。#include iostream #include queue #include vector struct Node { int id; int dist; // 注意这个符号我们希望 dist 越小越靠顶 bool operator(const Node other) const { return dist other.dist; // 小顶堆效果 } }; int main() { std::priority_queueNode pq; // 不需要任何额外模板参数 pq.push({1, 5}); pq.push({2, 4}); pq.push({3, 1}); pq.push({4, 3}); while (!pq.empty()) { auto node pq.top(); std::cout node.id node.dist \n; pq.pop(); } return 0; }输出是3 1、4 3、2 4、1 5。这种方式写 Dijkstra 的堆优化时特别顺手因为结构体里可以塞更多信息比如除了id和dist还想塞一个path标志位。直接用pair就太局促了。缺点也很现实你必须修改节点的类型定义有些场景下pair是既有的不方便再包一层结构体这时候就得回到前两种方式。另外需要注意operator重载的语义必须是“严格弱序”不能出现同时a b和b a都为真的情况。用dist作为比较字段时如果两个节点dist相等比较器应该返回false让堆认为它们“等价”否则可能产生未定义行为。我把三种方式的适用场景整理成了一张表方便你根据实际情况快速决策方式核心写法适用场景是否需要额外模板参数可维护性函数对象struct 重载 operator()多处复用、比较逻辑复杂、需携带状态是高lambda声明 lambda decltype刷题、局部使用、逻辑简单是中重载 operator自定义结构体Dijkstra、节点带额外属性、不想写第三个模板参数否高3. 排序方向的底层逻辑priority_queue 为什么和 sort“反着来”3.1 堆的核心规则比较函数决定的是“父节点优先权”这一节是最容易让人混淆的地方。很多人在sort里写return a b知道这是升序也就是小的在前。但到了priority_queue天然以为return a b是让“小的优先”结果每次top()弹出的是最大的直接懵。要搞清楚这件事得先理解堆的内部结构。priority_queue默认是最大堆底层是一棵完全二叉树存储在vector里。堆的性质是父节点的优先级高于它的两个孩子节点。而这里的“高于”不是天然的大小关系而是由你传入的Compare决定的。Compare的定义规则是Compare(a, b)返回true表示a的优先级低于b也就是说a应该排在b的下面。把这个规则放到堆排序里每次堆顶元素是优先级最高的那个。举个例子默认的Compare是std::lesspairint,int它等价于a.first b.first || (a.first b.first a.second b.second)。这个表达式返回true时表示a比b“小”。但是因为返回true代表a优先级更低所以堆会把“更大”的元素推到顶部。这就是为什么默认情况下3 1这样的 pair 会跑到堆顶。如果你用std::greaterpairint,int作为Compare那么a比b“大”时返回true也就是a优先级更低最终堆顶反而是“最小”的元素形成小顶堆。这个逻辑你品一下是不是和sort的方向完全反过来3.2 用模板参数推导记忆less 是大顶堆greater 是小顶堆我总结了一套非常容易记忆的口诀priority_queue的Compare参数写成less就是大顶堆写成greater就是小顶堆。不管元素是int还是pair这条都成立。priority_queueint默认lessint堆顶是最大值。priority_queueint, vectorint, greaterint堆顶是最小值。对于pairint, intpriority_queuepairint,int, vectorpairint,int, greaterpairint,int就是一个按字典序的小顶堆。first最小的靠顶first相同则second最小的靠顶。那么自定义排序时怎么反向设计我来列一个思维框架先明确你想要什么样的堆小顶堆还是大顶堆确定比较的字段是pair.first还是pair.second或者是它们的组合以你想放到堆顶的实体作为“高优先级”反过来写比较器如果想让a优先于b则比较器要求Compare(a, b)返回falseCompare(b, a)返回true。举一个直观例子我想让pair.second最小者置顶也就是“second 越小优先级越高”。按照上面第三条a的second比b的second小a应该优先那么Compare(b, a)要返回true即b.second a.second为真。为了通用我直接写return a.second b.second;含义是“如果 a 的 second 大于 b 的 second说明 a 优先级更低”。这就是正确的写法也印证了第 2 节里对应小顶堆的说法。我自己在写的时候还有一个习惯注释里一定写清楚“小顶堆”“大顶堆”“按哪个字段排”而不是只写代码。因为一周后回看代码人很容易忘记当时设计的方向。注意sort的比较器与堆完全相反二者千万不要互相套用。如果你在sort里写的升序比较器直接复制到priority_queue得到的不是期望的降序而是一个行为完全相反的堆。4. 实战应用Dijkstra 堆优化和 Top K 问题4.1 Dijkstra距离优先的 pair 排序Dijkstra 是最经典的堆优化场景。算法要求每次选出“当前未访问节点中距离源点最近”的节点。这里你需要一个小顶堆节点按照“当前距离”排序。很多人的初始写法是这样的using PII std::pairint, int; // {distance, node} std::priority_queuePII, std::vectorPII, std::greaterPII pq; pq.push({0, src});这个写法本身没问题因为greaterPII会形成按first距离从小到大排列的堆first相同再按node排。但如果你不对node的顺序有要求这已经是最简洁的写法。问题出在下面场景如果距离不是放在first而是放在second比如你想让节点编号占first那么必须自定义比较器。#include iostream #include queue #include vector #include utility #include climits using PII std::pairint, int; struct Cmp { bool operator()(const PII a, const PII b) const { return a.second b.second; // 按 second距离小顶堆 } }; void dijkstra(const std::vectorstd::vectorPII graph, int src) { int n (int)graph.size(); std::vectorint dist(n, INT_MAX); dist[src] 0; std::priority_queuePII, std::vectorPII, Cmp pq; // 或者 lambda 写法 // auto cmp [](const PII a, const PII b) { return a.second b.second; }; // std::priority_queuePII, std::vectorPII, decltype(cmp) pq(cmp); pq.push({src, 0}); while (!pq.empty()) { auto [node, d] pq.top(); pq.pop(); if (d ! dist[node]) continue; // 剪枝跳过过期元素 for (auto [neighbor, weight] : graph[node]) { if (dist[node] weight dist[neighbor]) { dist[neighbor] dist[node] weight; pq.push({neighbor, dist[neighbor]}); } } } }这里有几个细节值得关注if (d ! dist[node]) continue;是一个“惰性删除”技巧。堆里可能残留过期的元素它们的距离不是最新的弹出时直接跳过。这个技巧避免了你手动维护一个“已删除”集合代码更简洁。pair 的顺序我故意设计成{node, dist}然后让比较器按second排序。这样在访问top()时你可以直接用结构化绑定auto [node, d]取出节点和距离语义比{dist, node}更符合直觉。如果你按{dist, node}存储再配合greaterPII虽然代码更少但当有多个节点距离相同时它们会按node再排一次这通常是没必要的反而会影响性能虽然影响很小。自定义比较器就可以完全按距离排不关心第二个字段。我实测过在大规模图上比如 10 万节点、20 万条边这两种写法运行时间几乎无差别。但对于代码可读性来说{node, dist} 自定义比较器更友好因为top()取出来的第一个元素永远是节点编号不需要再去记忆“第一个是距离还是节点”。这一点在写长算法时非常有帮助。4.2 Top Kfirst 和 second 的优先级取舍Top K 问题也是 priority_queue 的拿手好戏。给你一堆pairint, int每个 pair 表示某个元素出现的次数second和它的编号first你需要找出出现次数最多的 K 个怎么办直观思路是用一个小顶堆堆内维护当前出现次数“最少”的元素当堆大小超过 K 时弹出堆顶。这样就保证堆里始终是目前出现次数最大的 K 个。比较器按second排序也就是出现次数。#include iostream #include queue #include vector #include utility using PII std::pairint, int; void topKFrequent(const std::vectorPII data, int k) { auto cmp [](const PII a, const PII b) { return a.second b.second; // 小顶堆second 小的靠顶 }; std::priority_queuePII, std::vectorPII, decltype(cmp) pq(cmp); for (auto item : data) { pq.push(item); if ((int)pq.size() k) { pq.pop(); // 弹出当前出现次数最少的 } } while (!pq.empty()) { auto [id, count] pq.top(); std::cout id count \n; pq.pop(); } }你可能会问为什么不用大顶堆直接来top()因为大顶堆只能帮你取到最大值取不到第 K 大的。小顶堆维护窗口的代价更低每次堆的大小不超过 K插入和弹出的复杂度都是O(log K)整体是O(N log K)。这里真正考察你对Compare方向理解的地方是cmp里写a.second b.second在小顶堆中second最小的元素在堆顶因而当堆满 K 个元素时堆顶代表的是“K 个最大元素中最小的那一个”。这个过程既利用了priority_queue的自动调整又通过自定义比较器把关注点集中在second上first只是作为一个附带信息存着不参与比较。Top K 场景和 Dijkstra 场景有一点不同Dijkstra 中你可能只关心first或second单一字段Top K 则经常需要你“同时记录编号和次数”这时候pair是天然的数据结构。自定义排序的价值在这里体现得非常直接你完全掌控比较规则不用为了迁就默认排序而强行把“次数”塞进first。5. 常见坑点与排查技巧实录5.1 lambda 写法编译报错decltype 类型不匹配有一个非常典型的问题很多初学者这样写auto cmp [](const std::pairint, int a, const std::pairint, int b) { return a.second b.second; }; // 错误没有把 cmp 传给构造函数 std::priority_queuestd::pairint, int, std::vectorstd::pairint, int, decltype(cmp) pq;在 C20 之前这会直接编译失败报错信息大概类似use of deleted function或no matching constructor。原因就是 lambda 闭包类型通常不是默认构造的priority_queue默认构造时无法构建比较器。正确写法是std::priority_queuestd::pairint, int, std::vectorstd::pairint, int, decltype(cmp) pq(cmp);还有一种情况是 lambda 捕获了外部变量int offset 10; auto cmp [offset](const std::pairint, int a, const std::pairint, int b) { return a.second offset b.second offset; };如果不在构造函数里传入cmp那问题更大因为捕获了状态的 lambda 连类型都不一样了。凡是遇到 lambda 作为比较器务必养成“初始化时把 lambda 对象传给构造函数”的肌肉记忆。5.2 greaterpairint, int 与自定义结构体的区别std::greaterstd::pairint, int可以直接用它的比较逻辑就是字典序的反转先比first再比secondfirst较小者靠顶。如果你对两个字段都无所谓排序顺序直接用greaterpairint,int最省事。但如果你只想按second排序greaterpairint,int就做不到。原因是它无法只关注一个字段。很多人用greater试完之后发现排序结果不对才回来学自定义比较器。另外std::pair自己有operator和operator但不建议你去重载std::pair的运算符因为pair在std命名空间里随意特化标准库的运算符可能导致未定义行为或代码污染。如果你想用重载operator的方式正确做法是像第 2.3 节那样自己定义一个struct Node。5.3 比较器必须满足严格弱序这是很多人忽略的坑。Compare必须满足“严格弱序”的要求简单来说Compare(a, a)必须为false。如果Compare(a, b)为true则Compare(b, a)必须为false。传递性如果a b且b c那么a c应该成立。举个反例假如我写了一个比较器当两个second相等时返回true这就是严格弱序的叛徒可能导致堆的关键操作出现未定义行为轻则排序结果不符合预期重则直接运行崩溃。// 错误示例 struct BadCmp { bool operator()(const std::pairint, int a, const std::pairint, int b) const { return a.second b.second; // 相等时也返回 true } };正确写法是return a.second b.second;或return a.second b.second;相等时返回false。所以写比较器的一个通用准则是只在明确的前后关系下返回true相等时一律返回false。如果你需要“先按第二字段降序第二字段相同再按第一字段排”比较器可以这样写struct Cmp { bool operator()(const std::pairint, int a, const std::pairint, int b) const { if (a.second ! b.second) return a.second b.second; // 大顶堆按 second return a.first b.first; // second 相同时按 first 排序 } };这种多重条件的比较器在真实项目里非常常见比如任务调度可能先按优先级再按创建时间再按任务 ID。pair只能放两个字段真正复杂情况我更建议用struct来代替。5.4 排查技巧用打印法快速验证排序方向当你不确定自己的排序方向对不对时最快的排查方式不是看文档而是写一个十行的小程序往堆里塞三四个有对比性的元素直接top()和pop()打印出来。我推荐的验证模板是这样的#include iostream #include queue #include vector #include utility void testPriorityQueue() { auto cmp [](const std::pairint, int a, const std::pairint, int b) { return a.second b.second; }; std::priority_queuestd::pairint, int, std::vectorstd::pairint, int, decltype(cmp) pq(cmp); pq.push({1, 10}); pq.push({2, 5}); pq.push({3, 8}); pq.push({4, 1}); while (!pq.empty()) { auto [id, val] pq.top(); std::cout id , val ; pq.pop(); } std::cout \n; }如果输出是4,1 2,5 3,8 1,10说明是小顶堆效果符合a.second b.second。如果输出是1,10 3,8 2,5 4,1说明是大顶堆效果。这个调试方法我强烈建议收藏。每次换比较器时你都跑一遍五秒钟就能确认方向不用靠猜。5.5 老生常谈但很多人不知比较器不能访问私有成员如果你把pair换成自定的结构体而结构体内有私有成员比较器又定义在结构体外部就可能导致访问权限错误。解决办法是要么把成员设置为public要么在结构体内部声明友元函数。实际中我一般让 Node 就是一个纯数据聚合体所有字段public根本不用搞什么封装。所谓“简单结构体”就是为了方便访问没必要把简单问题复杂化。6. 个人经验总结如果你现在要我把这一整篇文章浓缩成几条可执行的建议我会这么说能用greaterpairint,int解决就不自定义比如只要按first小顶堆直接一行搞定。priority_queuepairint,int, vectorpairint,int, greaterpairint,int是我刷算法题时最常用的模板之一。需要按second或组合排序时优先用 lambda代码短意图直接如果比较规则要在多个函数间复用就改成函数对象。Dijkstra 这种场景强烈建议自定义struct Node重载operator把距离和节点 ID 做成字段再顺手加上int id, dist;这样的语义化命名阅读起来比pairint,int舒服得多。排序方向一定要靠验证来记别靠背。写一个能打印的小堆三分钟跑完就清楚了。之后这个方向感就会内化再也不用每次踩坑。最后再分享一个小技巧priority_queue弹出的“最大值”或“最小值”其实取决于你传入的比较器但push和pop的时间复杂度始终是O(log N)。也就是说无论你怎么折腾比较器堆的性能特性都不变设计排序算法的自由度比你想象中要大得多。当你发现某些场景下比较器很别扭时不要硬凑回头想想是不是数据结构选型有问题也许你需要的是set或者sort加vector不一定非得是堆。 C++ priority_queue 与 pair 自定义排序：三种写法及方向详解
先说我自己的感受priority_queue配pair这件事几乎是每个写 C 图论和算法题的人都会撞上的墙。默认规则能跑一旦要按second排、按权值排、或者做小顶堆立刻一堆编译错误和诡异行为。这篇文章把我这几年在项目里和刷题时踩过的排序相关的坑、用过的三种写法、以及大小顶堆方向混淆的底层逻辑一次性理清楚。1. 问题场景为什么 pair 会频繁出现在 priority_queue 里1.1 默认排序的“意外”与局限std::pair是 C 里最常见的一对一组合容器priority_queue又是自带堆结构的优先级容器两者结合最常见的场景就是——把“节点编号 权值”或者“起始点 终点”打包放进堆里。默认情况下priority_queue直接用std::less来比较元素而std::pair的比较规则是字典序先比first再比second。先看一段最简单的代码#include iostream #include queue #include utility int main() { std::priority_queuestd::pairint, int pq; pq.push({1, 5}); pq.push({2, 4}); pq.push({1, 3}); pq.push({3, 1}); while (!pq.empty()) { auto [a, b] pq.top(); std::cout a b \n; pq.pop(); } return 0; }这段代码输出的顺序是什么是3 1、2 4、1 5、1 3。为什么同样的first 15排在3前面因为pair先比firstfirst相等就比second。也就是说默认规则下大顶堆由first决定first相同再接second。问题就来了在很多实际场景里我只想按second排序或者想实现一个小顶堆。比如 Dijkstra 算法中pairint, int的两个元素分别是“路径长度”和“节点编号”如果first是路径长度默认大顶堆就完全不符合需求因为 Dijkstra 每次要取的是“当前距离最短”的节点需要的是小顶堆而且要按first排序。这时候你就必须自定义排序算法。1.2 自定义排序的核心难点在哪priority_queue的模板签名长这样templateclass T, class Container std::vectorT, class Compare std::lesstypename Container::value_type class priority_queue;三个模板参数分别是元素类型、底层容器、比较器。Compare是一个可调用对象默认用std::less。很多人卡住的第一个点Compare的参数写反了或者 lambda 的写法不知道要传入构造函数。第二个难点就是方向问题。这个我在第 3 节专门讲这里先记住一个结论priority_queue的比较器返回true时表示第一个参数的优先级低于第二个参数也就是它会待在堆的更下方。这个规则和std::sort完全相反超多人在这里翻车。第三个难点是pair本身不是自定义类型你不能给它写成员形式的operator只能通过第三方的比较方式来影响堆的排序。所以接下来要讲的三种方式本质上都是提供一个“外部比较器”。2. 自定义排序的三把刀仿函数、lambda、重载运算符2.1 方法一函数对象仿函数写法函数对象是最经典、兼容性最好的写法。定义一个结构体重载operator()然后把结构体类型作为priority_queue的第三个模板参数。比如我要实现一个“按second从小到大排”的堆也就是second越小越靠顶#include iostream #include queue #include utility #include vector struct CmpBySecond { bool operator()(const std::pairint, int a, const std::pairint, int b) const { return a.second b.second; // 注意这是小顶堆逻辑 } }; int main() { std::priority_queuestd::pairint, int, std::vectorstd::pairint, int, CmpBySecond pq; pq.push({1, 5}); pq.push({2, 4}); pq.push({1, 3}); pq.push({3, 1}); while (!pq.empty()) { auto [a, b] pq.top(); std::cout a b \n; pq.pop(); } return 0; }输出是3 1、1 3、2 4、1 5。如果你想要大顶堆second越大越靠顶就把operator()里的改成bool operator()(const std::pairint, int a, const std::pairint, int b) const { return a.second b.second; // 大顶堆逻辑 }这里有一个非常关键的点如果你直接写return a.second b.second直觉上可能会觉得这是“升序”但在priority_queue里这个比较器会让second小的靠顶也就是小顶堆效果。很多初学者在这里纠结半天我建议直接做试验写两个小例子一个一个记住结果即可。实践经验比死记规则更靠谱。函数对象的优点是可以额外携带状态比如根据某个全局标志位决定比较规则。缺点就是代码量稍微多几行但可读性其实是最好的团队协作时一眼就能看懂意图。2.2 方法二lambda 表达式写法lambda 是写快速原型和刷题时最常用的方式。但必须注意因为 lambda 的闭包类型是匿名的、不可默认构造的所以你不能只把 lambda 类型传给模板参数还必须把 lambda 对象传入构造函数。正确写法#include iostream #include queue #include utility #include vector int main() { auto cmp [](const std::pairint, int a, const std::pairint, int b) { return a.second b.second; // 小顶堆second 小的靠顶 }; std::priority_queuestd::pairint, int, std::vectorstd::pairint, int, decltype(cmp) pq(cmp); // 必须把 cmp 传进去 pq.push({1, 5}); pq.push({2, 4}); pq.push({1, 3}); pq.push({3, 1}); while (!pq.empty()) { auto [a, b] pq.top(); std::cout a b \n; pq.pop(); } return 0; }错误写法只写decltype(cmp)却不传cmp给构造函数这会导致编译错误。因为 lambda 类型没有默认构造函数。这里很多人栽过我当年也栽过编译器的报错信息还特别长容易让人懵。如果 lambda 是空捕获列表[]也就是不捕获任何变量那么实际上它在 C20 之后是可以默认构造的但为了兼容老标准最好的习惯仍然是“无论是否捕获都显式把 lambda 对象传给构造函数”。这样代码在所有启用 C11 以上的环境都能稳定编译。我个人的建议是如果比较逻辑简单lambda 可以如果比较逻辑超过三行或者要在多个地方复用还是用函数对象吧省得每次都要复制粘贴 lambda。2.3 方法三重载 operator让 pair 变成“可排序的节点”第三种方式思路不同不直接给pair写比较器而是把pair包装成一个自定义结构体并重载它的operator。这样一来堆本身根本不需要第三个模板参数用默认的std::less就会自动调用结构体的运算符。#include iostream #include queue #include vector struct Node { int id; int dist; // 注意这个符号我们希望 dist 越小越靠顶 bool operator(const Node other) const { return dist other.dist; // 小顶堆效果 } }; int main() { std::priority_queueNode pq; // 不需要任何额外模板参数 pq.push({1, 5}); pq.push({2, 4}); pq.push({3, 1}); pq.push({4, 3}); while (!pq.empty()) { auto node pq.top(); std::cout node.id node.dist \n; pq.pop(); } return 0; }输出是3 1、4 3、2 4、1 5。这种方式写 Dijkstra 的堆优化时特别顺手因为结构体里可以塞更多信息比如除了id和dist还想塞一个path标志位。直接用pair就太局促了。缺点也很现实你必须修改节点的类型定义有些场景下pair是既有的不方便再包一层结构体这时候就得回到前两种方式。另外需要注意operator重载的语义必须是“严格弱序”不能出现同时a b和b a都为真的情况。用dist作为比较字段时如果两个节点dist相等比较器应该返回false让堆认为它们“等价”否则可能产生未定义行为。我把三种方式的适用场景整理成了一张表方便你根据实际情况快速决策方式核心写法适用场景是否需要额外模板参数可维护性函数对象struct 重载 operator()多处复用、比较逻辑复杂、需携带状态是高lambda声明 lambda decltype刷题、局部使用、逻辑简单是中重载 operator自定义结构体Dijkstra、节点带额外属性、不想写第三个模板参数否高3. 排序方向的底层逻辑priority_queue 为什么和 sort“反着来”3.1 堆的核心规则比较函数决定的是“父节点优先权”这一节是最容易让人混淆的地方。很多人在sort里写return a b知道这是升序也就是小的在前。但到了priority_queue天然以为return a b是让“小的优先”结果每次top()弹出的是最大的直接懵。要搞清楚这件事得先理解堆的内部结构。priority_queue默认是最大堆底层是一棵完全二叉树存储在vector里。堆的性质是父节点的优先级高于它的两个孩子节点。而这里的“高于”不是天然的大小关系而是由你传入的Compare决定的。Compare的定义规则是Compare(a, b)返回true表示a的优先级低于b也就是说a应该排在b的下面。把这个规则放到堆排序里每次堆顶元素是优先级最高的那个。举个例子默认的Compare是std::lesspairint,int它等价于a.first b.first || (a.first b.first a.second b.second)。这个表达式返回true时表示a比b“小”。但是因为返回true代表a优先级更低所以堆会把“更大”的元素推到顶部。这就是为什么默认情况下3 1这样的 pair 会跑到堆顶。如果你用std::greaterpairint,int作为Compare那么a比b“大”时返回true也就是a优先级更低最终堆顶反而是“最小”的元素形成小顶堆。这个逻辑你品一下是不是和sort的方向完全反过来3.2 用模板参数推导记忆less 是大顶堆greater 是小顶堆我总结了一套非常容易记忆的口诀priority_queue的Compare参数写成less就是大顶堆写成greater就是小顶堆。不管元素是int还是pair这条都成立。priority_queueint默认lessint堆顶是最大值。priority_queueint, vectorint, greaterint堆顶是最小值。对于pairint, intpriority_queuepairint,int, vectorpairint,int, greaterpairint,int就是一个按字典序的小顶堆。first最小的靠顶first相同则second最小的靠顶。那么自定义排序时怎么反向设计我来列一个思维框架先明确你想要什么样的堆小顶堆还是大顶堆确定比较的字段是pair.first还是pair.second或者是它们的组合以你想放到堆顶的实体作为“高优先级”反过来写比较器如果想让a优先于b则比较器要求Compare(a, b)返回falseCompare(b, a)返回true。举一个直观例子我想让pair.second最小者置顶也就是“second 越小优先级越高”。按照上面第三条a的second比b的second小a应该优先那么Compare(b, a)要返回true即b.second a.second为真。为了通用我直接写return a.second b.second;含义是“如果 a 的 second 大于 b 的 second说明 a 优先级更低”。这就是正确的写法也印证了第 2 节里对应小顶堆的说法。我自己在写的时候还有一个习惯注释里一定写清楚“小顶堆”“大顶堆”“按哪个字段排”而不是只写代码。因为一周后回看代码人很容易忘记当时设计的方向。注意sort的比较器与堆完全相反二者千万不要互相套用。如果你在sort里写的升序比较器直接复制到priority_queue得到的不是期望的降序而是一个行为完全相反的堆。4. 实战应用Dijkstra 堆优化和 Top K 问题4.1 Dijkstra距离优先的 pair 排序Dijkstra 是最经典的堆优化场景。算法要求每次选出“当前未访问节点中距离源点最近”的节点。这里你需要一个小顶堆节点按照“当前距离”排序。很多人的初始写法是这样的using PII std::pairint, int; // {distance, node} std::priority_queuePII, std::vectorPII, std::greaterPII pq; pq.push({0, src});这个写法本身没问题因为greaterPII会形成按first距离从小到大排列的堆first相同再按node排。但如果你不对node的顺序有要求这已经是最简洁的写法。问题出在下面场景如果距离不是放在first而是放在second比如你想让节点编号占first那么必须自定义比较器。#include iostream #include queue #include vector #include utility #include climits using PII std::pairint, int; struct Cmp { bool operator()(const PII a, const PII b) const { return a.second b.second; // 按 second距离小顶堆 } }; void dijkstra(const std::vectorstd::vectorPII graph, int src) { int n (int)graph.size(); std::vectorint dist(n, INT_MAX); dist[src] 0; std::priority_queuePII, std::vectorPII, Cmp pq; // 或者 lambda 写法 // auto cmp [](const PII a, const PII b) { return a.second b.second; }; // std::priority_queuePII, std::vectorPII, decltype(cmp) pq(cmp); pq.push({src, 0}); while (!pq.empty()) { auto [node, d] pq.top(); pq.pop(); if (d ! dist[node]) continue; // 剪枝跳过过期元素 for (auto [neighbor, weight] : graph[node]) { if (dist[node] weight dist[neighbor]) { dist[neighbor] dist[node] weight; pq.push({neighbor, dist[neighbor]}); } } } }这里有几个细节值得关注if (d ! dist[node]) continue;是一个“惰性删除”技巧。堆里可能残留过期的元素它们的距离不是最新的弹出时直接跳过。这个技巧避免了你手动维护一个“已删除”集合代码更简洁。pair 的顺序我故意设计成{node, dist}然后让比较器按second排序。这样在访问top()时你可以直接用结构化绑定auto [node, d]取出节点和距离语义比{dist, node}更符合直觉。如果你按{dist, node}存储再配合greaterPII虽然代码更少但当有多个节点距离相同时它们会按node再排一次这通常是没必要的反而会影响性能虽然影响很小。自定义比较器就可以完全按距离排不关心第二个字段。我实测过在大规模图上比如 10 万节点、20 万条边这两种写法运行时间几乎无差别。但对于代码可读性来说{node, dist} 自定义比较器更友好因为top()取出来的第一个元素永远是节点编号不需要再去记忆“第一个是距离还是节点”。这一点在写长算法时非常有帮助。4.2 Top Kfirst 和 second 的优先级取舍Top K 问题也是 priority_queue 的拿手好戏。给你一堆pairint, int每个 pair 表示某个元素出现的次数second和它的编号first你需要找出出现次数最多的 K 个怎么办直观思路是用一个小顶堆堆内维护当前出现次数“最少”的元素当堆大小超过 K 时弹出堆顶。这样就保证堆里始终是目前出现次数最大的 K 个。比较器按second排序也就是出现次数。#include iostream #include queue #include vector #include utility using PII std::pairint, int; void topKFrequent(const std::vectorPII data, int k) { auto cmp [](const PII a, const PII b) { return a.second b.second; // 小顶堆second 小的靠顶 }; std::priority_queuePII, std::vectorPII, decltype(cmp) pq(cmp); for (auto item : data) { pq.push(item); if ((int)pq.size() k) { pq.pop(); // 弹出当前出现次数最少的 } } while (!pq.empty()) { auto [id, count] pq.top(); std::cout id count \n; pq.pop(); } }你可能会问为什么不用大顶堆直接来top()因为大顶堆只能帮你取到最大值取不到第 K 大的。小顶堆维护窗口的代价更低每次堆的大小不超过 K插入和弹出的复杂度都是O(log K)整体是O(N log K)。这里真正考察你对Compare方向理解的地方是cmp里写a.second b.second在小顶堆中second最小的元素在堆顶因而当堆满 K 个元素时堆顶代表的是“K 个最大元素中最小的那一个”。这个过程既利用了priority_queue的自动调整又通过自定义比较器把关注点集中在second上first只是作为一个附带信息存着不参与比较。Top K 场景和 Dijkstra 场景有一点不同Dijkstra 中你可能只关心first或second单一字段Top K 则经常需要你“同时记录编号和次数”这时候pair是天然的数据结构。自定义排序的价值在这里体现得非常直接你完全掌控比较规则不用为了迁就默认排序而强行把“次数”塞进first。5. 常见坑点与排查技巧实录5.1 lambda 写法编译报错decltype 类型不匹配有一个非常典型的问题很多初学者这样写auto cmp [](const std::pairint, int a, const std::pairint, int b) { return a.second b.second; }; // 错误没有把 cmp 传给构造函数 std::priority_queuestd::pairint, int, std::vectorstd::pairint, int, decltype(cmp) pq;在 C20 之前这会直接编译失败报错信息大概类似use of deleted function或no matching constructor。原因就是 lambda 闭包类型通常不是默认构造的priority_queue默认构造时无法构建比较器。正确写法是std::priority_queuestd::pairint, int, std::vectorstd::pairint, int, decltype(cmp) pq(cmp);还有一种情况是 lambda 捕获了外部变量int offset 10; auto cmp [offset](const std::pairint, int a, const std::pairint, int b) { return a.second offset b.second offset; };如果不在构造函数里传入cmp那问题更大因为捕获了状态的 lambda 连类型都不一样了。凡是遇到 lambda 作为比较器务必养成“初始化时把 lambda 对象传给构造函数”的肌肉记忆。5.2 greaterpairint, int 与自定义结构体的区别std::greaterstd::pairint, int可以直接用它的比较逻辑就是字典序的反转先比first再比secondfirst较小者靠顶。如果你对两个字段都无所谓排序顺序直接用greaterpairint,int最省事。但如果你只想按second排序greaterpairint,int就做不到。原因是它无法只关注一个字段。很多人用greater试完之后发现排序结果不对才回来学自定义比较器。另外std::pair自己有operator和operator但不建议你去重载std::pair的运算符因为pair在std命名空间里随意特化标准库的运算符可能导致未定义行为或代码污染。如果你想用重载operator的方式正确做法是像第 2.3 节那样自己定义一个struct Node。5.3 比较器必须满足严格弱序这是很多人忽略的坑。Compare必须满足“严格弱序”的要求简单来说Compare(a, a)必须为false。如果Compare(a, b)为true则Compare(b, a)必须为false。传递性如果a b且b c那么a c应该成立。举个反例假如我写了一个比较器当两个second相等时返回true这就是严格弱序的叛徒可能导致堆的关键操作出现未定义行为轻则排序结果不符合预期重则直接运行崩溃。// 错误示例 struct BadCmp { bool operator()(const std::pairint, int a, const std::pairint, int b) const { return a.second b.second; // 相等时也返回 true } };正确写法是return a.second b.second;或return a.second b.second;相等时返回false。所以写比较器的一个通用准则是只在明确的前后关系下返回true相等时一律返回false。如果你需要“先按第二字段降序第二字段相同再按第一字段排”比较器可以这样写struct Cmp { bool operator()(const std::pairint, int a, const std::pairint, int b) const { if (a.second ! b.second) return a.second b.second; // 大顶堆按 second return a.first b.first; // second 相同时按 first 排序 } };这种多重条件的比较器在真实项目里非常常见比如任务调度可能先按优先级再按创建时间再按任务 ID。pair只能放两个字段真正复杂情况我更建议用struct来代替。5.4 排查技巧用打印法快速验证排序方向当你不确定自己的排序方向对不对时最快的排查方式不是看文档而是写一个十行的小程序往堆里塞三四个有对比性的元素直接top()和pop()打印出来。我推荐的验证模板是这样的#include iostream #include queue #include vector #include utility void testPriorityQueue() { auto cmp [](const std::pairint, int a, const std::pairint, int b) { return a.second b.second; }; std::priority_queuestd::pairint, int, std::vectorstd::pairint, int, decltype(cmp) pq(cmp); pq.push({1, 10}); pq.push({2, 5}); pq.push({3, 8}); pq.push({4, 1}); while (!pq.empty()) { auto [id, val] pq.top(); std::cout id , val ; pq.pop(); } std::cout \n; }如果输出是4,1 2,5 3,8 1,10说明是小顶堆效果符合a.second b.second。如果输出是1,10 3,8 2,5 4,1说明是大顶堆效果。这个调试方法我强烈建议收藏。每次换比较器时你都跑一遍五秒钟就能确认方向不用靠猜。5.5 老生常谈但很多人不知比较器不能访问私有成员如果你把pair换成自定的结构体而结构体内有私有成员比较器又定义在结构体外部就可能导致访问权限错误。解决办法是要么把成员设置为public要么在结构体内部声明友元函数。实际中我一般让 Node 就是一个纯数据聚合体所有字段public根本不用搞什么封装。所谓“简单结构体”就是为了方便访问没必要把简单问题复杂化。6. 个人经验总结如果你现在要我把这一整篇文章浓缩成几条可执行的建议我会这么说能用greaterpairint,int解决就不自定义比如只要按first小顶堆直接一行搞定。priority_queuepairint,int, vectorpairint,int, greaterpairint,int是我刷算法题时最常用的模板之一。需要按second或组合排序时优先用 lambda代码短意图直接如果比较规则要在多个函数间复用就改成函数对象。Dijkstra 这种场景强烈建议自定义struct Node重载operator把距离和节点 ID 做成字段再顺手加上int id, dist;这样的语义化命名阅读起来比pairint,int舒服得多。排序方向一定要靠验证来记别靠背。写一个能打印的小堆三分钟跑完就清楚了。之后这个方向感就会内化再也不用每次踩坑。最后再分享一个小技巧priority_queue弹出的“最大值”或“最小值”其实取决于你传入的比较器但push和pop的时间复杂度始终是O(log N)。也就是说无论你怎么折腾比较器堆的性能特性都不变设计排序算法的自由度比你想象中要大得多。当你发现某些场景下比较器很别扭时不要硬凑回头想想是不是数据结构选型有问题也许你需要的是set或者sort加vector不一定非得是堆。