优先队列重载排序

### C++ 优先队列自定义排序规则 在 C++ 中，`std::priority_queue` 是一种容器适配器，默认情况下实现的是最大堆（即顶部元素是最大的）。如果需要改变其默认行为，则可以通过提供自定义比较函数来调整排序规则。 #### 方法一：使用仿函数 (Functor) 仿函数是一种重载了 `()` 运算符的结构体或类。下面是一个示例： ```cpp #include <iostream> #include <queue> struct CustomCompare { bool operator()(int a, int b) { return a > b; // 小于号表示最小堆，大于号表示最大堆 } }; int main() { std::priority_queue<int, std::vector<int>, CustomCompare> pq; pq.push(10); pq.push(3); pq.push(7); while (!pq.empty()) { std::cout << pq.top() << " "; pq.pop(); } return 0; } ``` 在这个例子中，我们创建了一个名为 `CustomCompare` 的仿函数，并将其作为第三个模板参数传递给 `std::priority_queue`[^1]。这使得优先队列按照升序排列（即最小堆）。 --- #### 方法二：使用 Lambda 表达式 Lambda 表达式可以简化代码编写过程。然而需要注意的是，在某些编译器版本下，lambda 可能无法直接用于模板参数。因此通常会先将 lambda 转换为标准函数对象再传入。 ```cpp #include <iostream> #include <queue> #include <functional> auto customComp = [](int a, int b) -> bool { return a > b; }; int main() { std::priority_queue<int, std::vector<int>, decltype(customComp)> pq(customComp); pq.push(10); pq.push(3); pq.push(7); while (!pq.empty()) { std::cout << pq.top() << " "; pq.pop(); } return 0; } ``` 这里通过 `decltype` 获取 lambda 类型并显式指定给优先队列第三参数位置[^4]。 --- #### 方法三：基于预定义的标准库比较器 C++ 标准库提供了两个常用的比较器：`std::less<T>` 和 `std::greater<T>`。它们分别对应降序和升序关系。 ```cpp #include <iostream> #include <queue> #include <vector> #include <functional> int main() { // 大顶堆（默认） std::priority_queue<int, std::vector<int>, std::less<int>> maxHeap; maxHeap.push(10); maxHeap.push(3); maxHeap.push(7); while (!maxHeap.empty()) { std::cout << maxHeap.top() << " "; maxHeap.pop(); } // 小顶堆 std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap; minHeap.push(10); minHeap.push(3); minHeap.push(7); while (!minHeap.empty()) { std::cout << minHeap.top() << " "; minHeap.pop(); } return 0; } ``` 这段程序展示了如何利用 `std::less` 构建大顶堆以及借助 `std::greater` 实现小顶堆的功能[^2]。 --- #### 总结 以上三种方法都可以用来定制化 `std::priority_queue` 的内部顺序逻辑。具体选择取决于实际需求和个人偏好。对于简单场景推荐采用内置比较器；而对于复杂业务则更适合运用仿函数甚至更灵活的 lambda 方案。