cpp 优先队列

### C++ 中优先队列的使用方法及示例 #### 1. 基本概念 `priority_queue` 是 C++ STL 提供的一种容器适配器，基于堆结构实现。它的主要特点是每次弹出操作都会返回当前队列中具有最高优先级的元素（默认情况下为最大值）。这种特性使其非常适合用于解决涉及动态排序的任务。 #### 2. 默认行为 在不指定任何额外参数的情况下，`priority_queue<int>` 将按照从大到小的顺序排列整数[^1]。这是因为它内部使用的是 `std::vector` 和 `std::less<T>` 来构建最大堆。 ```cpp #include <iostream> #include <queue> int main() { std::priority_queue<int> pq; pq.push(10); pq.push(30); pq.push(20); while (!pq.empty()) { std::cout << pq.top() << " "; // 输出：30 20 10 pq.pop(); } } ``` 上述代码展示了如何创建一个默认的最大堆并依次取出其中的元素。 #### 3. 自定义比较函数 如果希望改变默认的行为，比如让优先队列按从小到大的顺序存储数据，则可以传入第三个模板参数——一个自定义的比较函数或类实例。例如： ##### 使用标准库中的 `greater<>` 通过传递 `std::greater<T>` 可以反转默认的大顶堆逻辑，从而得到一个小顶堆。 ```cpp #include <iostream> #include <queue> #include <functional> int main() { std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap; minHeap.push(10); minHeap.push(30); minHeap.push(20); while (!minHeap.empty()) { std::cout << minHeap.top() << " "; // 输出：10 20 30 minHeap.pop(); } } ``` ##### 定义 Lambda 表达式作为比较器 还可以利用 lambda 函数来自定义复杂的比较规则。下面的例子展示了一个根据模运算结果决定优先级的优先队列。 ```cpp #include <iostream> #include <queue> #include <functional> int main() { auto cmp = [](int a, int b) -> bool { return (a % 10) > (b % 10); }; std::priority_queue<int, std::vector<int>, decltype(cmp)> customPQ(cmp); customPQ.push(19); customPQ.push(28); customPQ.push(37); while (!customPQ.empty()) { std::cout << customPQ.top() << " "; // 输出取决于具体输入和定制化规则 customPQ.pop(); } } ``` #### 4. 结构体/类支持 当需要管理更复杂的数据类型时，可以通过重载 `<` 运算符或者显式提供比较器来控制其排序方式[^2]。 ```cpp struct Node { int value; char label; friend bool operator<(const Node& lhs, const Node& rhs) { return lhs.value < rhs.value; // 大顶堆依据value字段降序排列 } }; int main() { std::priority_queue<Node> nodeQueue; nodeQueue.push(Node{5, 'A'}); nodeQueue.push(Node{1, 'B'}); while (!nodeQueue.empty()) { Node topNode = nodeQueue.top(); std::cout << "{" << topNode.label << ", " << topNode.value << "} "; nodeQueue.pop(); } // 输出可能类似于：{A, 5} {B, 1} } ``` #### 总结 以上介绍了几种常见的 `priority_queue` 的应用形式及其背后的原理。无论是简单的数值型还是较为复杂的对象集合都可以借助这一工具高效完成任务需求[^3]。