C++优先队列自定义排序方法

priority_queue默认为最大堆，通过自定义比较器可实现最小堆或复杂排序逻辑，如用std::greater或自定义functor、lambda按特定规则排序。

priority_queue在C++里默认是个最大堆，也就是说，它总是把最大的元素放在最前面，你一取就能拿到。但很多时候，我们需要的不是最大的，而是最小的，或者说，我们对“大小”的定义跟它默认的不一样。这时候，我们就需要给它一个“指南针”，告诉它怎么判断谁的优先级更高，这个指南针就是自定义排序。本质上，就是通过提供一个特定的比较器（comparator），来改变它内部堆的组织方式，让它按我们的规矩来排队。

解决方案

priority_queue是一个容器适配器，它基于底层容器（默认是std::vector）和比较器（默认是std::less<T>）来构建。要自定义排序，关键就在于修改它的第三个模板参数——Compare。

1. 实现最小堆（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
   }

2. 为自定义类型实现排序 当你的队列里放的是自定义的结构体或类对象时，比如一个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是最大堆，它能很好地解决“总是想拿到当前最大值”的问题。比如，你有一堆任务，每个任务有个“重要性”评分，你总是想优先处理最重要的。这种场景，默认行为完全够用。

但现实世界可没那么简单，优先级这东西，定义起来千变万化。

想想看，如果你在实现一个最短路径算法，比如Dijkstra，你需要一个优先队列来存储待处理的节点，并且每次都取出“距离源点最近”的那个节点。这里的“最近”显然是“最小”的概念，而默认的最大堆就帮不上忙了。你需要一个最小堆。

再比如，你可能在处理一个复杂的排班系统，员工有多个属性：工龄、绩效、加班意愿等等。你可能需要根据这些属性的组合来决定谁的优先级更高。比如，工龄越长优先级越高，如果工龄相同，再看绩效，绩效越高优先级越高。这种多条件、自定义逻辑的排序，默认的int或double比较根本无法满足，你必须自己写规则。

所以，默认行为不是不够用，而是它只覆盖了最基础、最普遍的需求。一旦你的“优先级”定义超出了简单的数值大小，或者你需要的是“最小”而不是“最大”时，自定义排序就成了你的救星。它赋予了你对数据“排序逻辑”的完全控制权，这在解决复杂算法问题和业务逻辑时，简直是不可或缺的能力。

如何为复杂数据结构实现自定义排序？

为复杂数据结构实现自定义排序，通常意味着你需要根据对象的多个成员变量，或者一些计算出来的属性来决定它们的相对顺序。这比简单的数值比较要精妙得多。

我一般会这么做：

1. 明确排序规则： 这是第一步，也是最关键的一步。你需要清晰地定义“A比B优先级高”到底意味着什么。例如，对于一个Player对象，你可能想先按等级（高等级优先），等级相同再按经验值（高经验值优先），经验值再相同就按ID（小ID优先）。

2. 选择比较器实现方式：

   • 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如果第一个对象应该被认为“小于”第二个对象（即优先级更低）。这个“小于”的定义完全由你掌控。

自定义排序时常见的误区与性能考量

在自定义priority_queue的排序逻辑时，我见过不少人，包括我自己，会踩一些坑。同时，性能也是一个需要注意的点。

常见误区：

1. 最大堆与最小堆的逻辑混淆： 这是最普遍的。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>来做个实验，看它们各自对应最大堆还是最小堆，然后根据这个理解去推导自定义逻辑。

2. 比较器不满足严格弱序（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内部的堆结构被破坏，从而产生不可预测的错误，调试起来会非常痛苦。

3. 参数传递效率问题： 在比较器中，如果你的自定义对象比较大，确保参数是以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;
       }
   };

性能考量：

1. 比较器复杂度： priority_queue的push和pop操作的时间复杂度是O(log N)，其中N是队列中的元素数量。这个log N是基于比较操作的次数。如果你的自定义比较器内部执行了非常复杂的计算（比如遍历一个列表，或者进行网络请求——当然，你不会这么做，但理论上），那么每次比较的常数时间就会变大，从而拉长整体操作时间。 所以，设计比较器时，尽量保持其内部逻辑简洁高效。避免在比较器中