priority_queue默认为最大堆，通过自定义比较器可实现最小堆或复杂排序逻辑，如用std::greater或自定义functor、lambda按特定规则排序。
priority_queue在C++里默认是个最大堆，也就是说，它总是把最大的元素放在最前面，你一取就能拿到。但很多时候，我们需要的不是最大的，而是最小的，或者说，我们对“大小”的定义跟它默认的不一样。这时候，我们就需要给它一个“指南针”，告诉它怎么判断谁的优先级更高，这个指南针就是自定义排序。本质上，就是通过提供一个特定的比较器（comparator），来改变它内部堆的组织方式，让它按我们的规矩来排队。
解决方案
priority_queue是一个容器适配器，它基于底层容器（默认是
std::vector）和比较器（默认是
std::less<T>）来构建。要自定义排序，关键就在于修改它的第三个模板参数——
Compare。
-
实现最小堆（Min-Heap） 这是最常见的自定义需求。
priority_queue
默认用std::less<T>
来比较，这意味着如果a < b
，那么a
的优先级就比b
低，b
会被放在更前面（形成最大堆）。如果想实现最小堆，我们希望a > b
时，a
的优先级比b
低，这样小的元素才能浮到顶部。所以，我们用std::greater<T>
作为比较器。#include <iostream> #include <queue> #include <vector> #include <functional> // For std::greater void minHeapExample() { std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq; min_pq.push(3); min_pq.push(1); min_pq.push(4); min_pq.push(1); min_pq.push(5); std::cout << "Min-Heap elements (smallest first): "; while (!min_pq.empty()) { std::cout << min_pq.top() << " "; min_pq.pop(); } std::cout << std::endl; // Output: 1 1 3 4 5 } -
为自定义类型实现排序 当你的队列里放的是自定义的结构体或类对象时，比如一个
Point
，你想根据它的某个成员变量（比如x
坐标）来决定优先级，这就需要更灵活的自定义比较器了。你可以使用：-
自定义结构体/类作为比较器（Functor） 定义一个结构体，重载
operator()
，让它接收两个你的对象，并返回一个bool
值，表示第一个对象是否“小于”第二个对象（即优先级是否更低）。记住，priority_queue
会根据这个“小于”来构建一个最大堆。如果你想让x
值小的优先级高（即最小堆），那么你的operator()
应该返回a.x > b.x
。#include <iostream> #include <queue> #include <vector> struct MyPoint { int x; int y; // 构造函数 MyPoint(int x_val, int y_val) : x(x_val), y(y_val) {} // 用于打印 void print() const { std::cout << "(" << x << "," << y << ")"; } }; // 自定义比较器：根据x值，x值越大优先级越高（最大堆） struct CompareMyPointMaxX { bool operator()(const MyPoint& a, const MyPoint& b) const { return a.x < b.x; // 如果a的x小于b的x，则a的优先级更低，b会排在前面 } }; // 自定义比较器：根据x值，x值越小优先级越高（最小堆） struct CompareMyPointMinX { bool operator()(const MyPoint& a, const MyPoint& b) const { return a.x > b.x; // 如果a的x大于b的x，则a的优先级更低，b会排在前面 } }; void customObjectExample() { std::priority_queue<MyPoint, std::vector<MyPoint>, CompareMyPointMaxX> pq_maxX; pq_maxX.push(MyPoint(10, 20)); pq_maxX.push(MyPoint(5, 30)); pq_maxX.push(MyPoint(15, 10)); std::cout << "Custom Max-Heap by X: "; while (!pq_maxX.empty()) { pq_maxX.top().print(); std::cout << " "; pq_maxX.pop(); } std::cout << std::endl; // Output: (15,10) (10,20) (5,30) std::priority_queue<MyPoint, std::vector<MyPoint>, CompareMyPointMinX> pq_minX; pq_minX.push(MyPoint(10, 20)); pq_minX.push(MyPoint(5, 30)); pq_minX.push(MyPoint(15, 10)); std::cout << "Custom Min-Heap by X: "; while (!pq_minX.empty()) { pq_minX.top().print(); std::cout << " "; pq_minX.pop(); } std::cout << std::endl; // Output: (5,30) (10,20) (15,10) } -
使用Lambda表达式（C++11及更高版本） 这是现代C++中非常简洁和灵活的方式。你可以在
priority_queue
的构造函数中直接传入一个lambda表达式。需要注意的是，因为lambda表达式本身是一个匿名类型，你不能直接把它作为模板参数。你需要先定义一个auto
变量来捕获这个lambda，或者使用decltype
。更常见且推荐的做法是，直接在构造时提供lambda，让编译器推导。#include <iostream> #include <queue> #include <vector> #include <functional> // For std::function (optional, but good for understanding) struct Task { int id; int priority; // 优先级值，越小表示优先级越高 Task(int i, int p) : id(i), priority(p) {} void print() const { std::cout << "[ID:" << id << ",P:" << priority << "]"; } }; void lambdaCustomSortExample() { // Lambda作为比较器：根据Task的priority值，值越小优先级越高（最小堆） // 注意：priority_queue默认是最大堆行为，所以如果希望priority值小的排在前面， // 那么lambda应该返回 'a.priority > b.priority'，表示a的优先级更低 auto cmp = [](const Task& a, const Task& b) { return a.priority > b.priority; // 如果a的优先级值比b大，则a的优先级更低 }; // 声明priority_queue时，需要将lambda的类型作为模板参数 // 通常做法是定义一个局部变量来捕获lambda，然后用decltype获取其类型 std::priority_queue<Task, std::vector<Task>, decltype(cmp)> task_pq(cmp); task_pq.push(Task(101, 5)); // 低优先级 task_pq.push(Task(102, 1)); // 高优先级 task_pq.push(Task(103, 3)); // 中优先级 std::cout << "Tasks by priority (smallest priority value first): "; while (!task_pq.empty()) { task_pq.top().print(); std::cout << " "; task_pq.pop(); } std::cout << std::endl; // Output: [ID:102,P:1] [ID:103,P:3] [ID:101,P:5] }在实际项目中，我个人更倾向于使用lambda，因为它写起来快，而且如果比较逻辑只用一次，代码也更集中。但如果比较逻辑复杂或者需要在多个地方复用，一个独立的functor类会是更好的选择，因为它有名字，可读性更强。
-
为什么需要自定义排序？默认行为不够用吗？
这个问题问得好，直击核心。默认的
priority_queue是最大堆，它能很好地解决“总是想拿到当前最大值”的问题。比如，你有一堆任务，每个任务有个“重要性”评分，你总是想优先处理最重要的。这种场景，默认行为完全够用。
立即学习“C++免费学习笔记（深入）”；
但现实世界可没那么简单，优先级这东西，定义起来千变万化。
想想看，如果你在实现一个最短路径算法，比如Dijkstra，你需要一个优先队列来存储待处理的节点，并且每次都取出“距离源点最近”的那个节点。这里的“最近”显然是“最小”的概念，而默认的最大堆就帮不上忙了。你需要一个最小堆。
再比如，你可能在处理一个复杂的排班系统，员工有多个属性：工龄、绩效、加班意愿等等。你可能需要根据这些属性的组合来决定谁的优先级更高。比如，工龄越长优先级越高，如果工龄相同，再看绩效，绩效越高优先级越高。这种多条件、自定义逻辑的排序，默认的
int或
double比较根本无法满足，你必须自己写规则。
所以，默认行为不是不够用，而是它只覆盖了最基础、最普遍的需求。一旦你的“优先级”定义超出了简单的数值大小，或者你需要的是“最小”而不是“最大”时，自定义排序就成了你的救星。它赋予了你对数据“排序逻辑”的完全控制权，这在解决复杂算法问题和业务逻辑时，简直是不可或缺的能力。
如何为复杂数据结构实现自定义排序？
为复杂数据结构实现自定义排序，通常意味着你需要根据对象的多个成员变量，或者一些计算出来的属性来决定它们的相对顺序。这比简单的数值比较要精妙得多。
我一般会这么做：
明确排序规则： 这是第一步，也是最关键的一步。你需要清晰地定义“A比B优先级高”到底意味着什么。例如，对于一个
Player
对象，你可能想先按等级（高等级优先），等级相同再按经验值（高经验值优先），经验值再相同就按ID（小ID优先）。-
选择比较器实现方式：
-
Functor（函数对象）： 定义一个独立的结构体，重载
operator()
。这种方式的好处是，比较逻辑被封装在一个有名字的类型里，可读性强，方便复用。如果你的比较器需要保存一些状态（比如一个阈值），functor也能轻松实现。 - Lambda表达式： 如果比较逻辑比较简单，或者只在特定地方使用一次，lambda表达式是绝佳的选择。它简洁、直接，代码内联，避免了额外定义一个类的开销。
我们来用一个更复杂的例子：
Student
，有score
和id
。我们希望score
高的优先级高，如果score
相同，id
小的优先级高。#include <iostream> #include <queue> #include <vector> struct Student { int id; int score; Student(int i, int s) : id(i), score(s) {} void print() const { std::cout << "[ID:" << id << ",Score:" << score << "]"; } }; // 方法一：使用Functor struct CompareStudent { bool operator()(const Student& a, const Student& b) const { // 优先比较分数：分数高的优先级高 (最大堆) if (a.score != b.score) { return a.score < b.score; // 如果a的分数比b低，则a的优先级更低 } // 分数相同，比较ID：ID小的优先级高 (最小堆) return a.id > b.id; // 如果a的ID比b大，则a的优先级更低 } }; void complexObjectFunctorExample() { std::priority_queue<Student, std::vector<Student>, CompareStudent> student_pq; student_pq.push(Student(101, 90)); student_pq.push(Student(102, 95)); student_pq.push(Student(103, 90)); // 分数相同，ID不同 student_pq.push(Student(104, 85)); std::cout << "Students by Score (desc), then ID (asc): "; while (!student_pq.empty()) { student_pq.top().print(); std::cout << " "; student_pq.pop(); } std::cout << std::endl; // Output: [ID:102,Score:95] [ID:101,Score:90] [ID:103,Score:90] [ID:104,Score:85] (这里ID101在103前面，因为101的ID更小，在分数相同的情况下优先级更高) } // 方法二：使用Lambda表达式 void complexObjectLambdaExample() { auto cmp_lambda = [](const Student& a, const Student& b) { if (a.score != b.score) { return a.score < b.score; // 分数高的优先级高 } return a.id > b.id; // ID小的优先级高 }; std::priority_queue<Student, std::vector<Student>, decltype(cmp_lambda)> student_pq_lambda(cmp_lambda); student_pq_lambda.push(Student(201, 88)); student_pq_lambda.push(Student(202, 92)); student_pq_lambda.push(Student(203, 88)); student_pq_lambda.push(Student(204, 92)); // 分数相同，ID不同 std::cout << "Students by Score (desc), then ID (asc) (Lambda): "; while (!student_pq_lambda.empty()) { student_pq_lambda.top().print(); std::cout << " "; student_pq_lambda.pop(); } std::cout << std::endl; // Output: [ID:202,Score:92] [ID:204,Score:92] [ID:201,Score:88] [ID:203,Score:88] }无论是Functor还是Lambda，核心都是实现一个二元谓词（binary predicate），它接收两个对象，并返回
true
如果第一个对象应该被认为“小于”第二个对象（即优先级更低）。这个“小于”的定义完全由你掌控。 -
Functor（函数对象）： 定义一个独立的结构体，重载
自定义排序时常见的误区与性能考量
在自定义
priority_queue的排序逻辑时，我见过不少人，包括我自己，会踩一些坑。同时，性能也是一个需要注意的点。
常见误区：
-
最大堆与最小堆的逻辑混淆： 这是最普遍的。
priority_queue
默认行为是最大堆，意味着top()
总是最大的。你的比较器Compare
，如果cmp(a, b)
返回true
，则表示a
的优先级比b
低，b
会排在a
前面。- 如果你想让“值越小优先级越高”（最小堆），那么当
a > b
时，a
的优先级应该更低，所以cmp(a, b)
应该返回true
。例如，return a.value > b.value;
。 - 如果你想让“值越大优先级越高”（最大堆），那么当
a < b
时，a
的优先级应该更低，所以cmp(a, b)
应该返回true
。例如，return a.value < b.value;
。 初学者经常会搞反，导致结果和预期相反。我通常会拿std::less<int>
和std::greater<int>
来做个实验，看它们各自对应最大堆还是最小堆，然后根据这个理解去推导自定义逻辑。
- 如果你想让“值越小优先级越高”（最小堆），那么当
-
比较器不满足严格弱序（Strict Weak Ordering）： 这是算法正确性的基石。一个有效的比较器必须满足：
-
非自反性：
cmp(x, x)
必须为false
。 -
反对称性： 如果
cmp(x, y)
为true
，则cmp(y, x)
必须为false
。 -
传递性： 如果
cmp(x, y)
为true
且cmp(y, z)
为true
，则cmp(x, z)
必须为true
。 -
等价性传递： 如果
x
和y
等价（即!cmp(x, y) && !cmp(y, x)
），且y
和z
等价，则x
和z
也必须等价。 违反这些规则会导致priority_queue
内部的堆结构被破坏，从而产生不可预测的错误，调试起来会非常痛苦。
-
非自反性：
-
参数传递效率问题： 在比较器中，如果你的自定义对象比较大，确保参数是以
const T&
的形式传递，而不是T
（按值传递）。按值传递会产生不必要的对象拷贝，这在频繁的比较操作中会显著降低性能。// 错误示例：按值传递，可能导致性能问题 struct BadCompare { bool operator()(MyBigObject a, MyBigObject b) const { // 注意这里没有const & // ... return a.value < b.value; } }; // 正确示例：按const引用传递 struct GoodCompare { bool operator()(const MyBigObject& a, const MyBigObject& b) const { // ... return a.value < b.value; } };
性能考量：
-
比较器复杂度：
priority_queue
的push
和pop
操作的时间复杂度是O(log N)
，其中N
是队列中的元素数量。这个log N
是基于比较操作的次数。如果你的自定义比较器内部执行了非常复杂的计算（比如遍历一个列表，或者进行网络请求——当然，你不会这么做，但理论上），那么每次比较的常数时间就会变大，从而拉长整体操作时间。 所以，设计比较器时，尽量保持其内部逻辑简洁高效。避免在比较器中
