优先级队列C++
时间: 2025-04-29 11:54:09 浏览: 26
### C++ 中实现优先级队列
在 C++ 中,`priority_queue` 是一种非常有用的容器适配器,它提供了对最大或最小元素的快速访问。为了创建一个优先级队列,通常需要包含 `<queue>` 头文件。
#### 定义与初始化
对于 `priority_queue<int> pq;` 的声明,默认情况下会构建一个大顶堆,即每次取出的最大值位于顶部。如果希望得到一个小顶堆,则可以通过指定第三个参数为 `std::greater<T>` 来改变其行为[^2]。
下面给出一段完整的代码用于演示如何定义并操作不同类型的优先级队列:
```cpp
#include <iostream>
#include <queue>
using namespace std;
// 构造大顶堆
void maxHeapExample() {
priority_queue<int> maxPQ;
// 插入一些整数值到大根堆中
maxPQ.push(1);
maxPQ.push(3);
maxPQ.push(2);
cout << "Max Heap Elements: ";
while (!maxPQ.empty()) {
cout << maxPQ.top() << ' ';
maxPQ.pop();
}
}
// 构造小顶堆
void minHeapExample() {
priority_queue<int, vector<int>, greater<int>> minPQ;
// 向小根堆插入相同的一组整数
minPQ.push(1);
minPQ.push(3);
minPQ.push(2);
cout << "\nMin Heap Elements: ";
while (!minPQ.empty()) {
cout << minPQ.top() << ' ';
minPQ.pop();
}
}
```
这段程序展示了两种不同的方式来实例化优先级队列——一个是基于默认设置的大顶堆,另一个是指定了比较函数的小顶堆。通过这种方式可以根据实际需求灵活选择所需的堆类型[^5]。
当涉及到更复杂的数据结构或者自定义对象作为队列元素时,可能还需要提供额外的信息给编译器知道怎样去比较这些元素之间的大小关系。这通常是通过对仿函数的支持完成的,比如上面提到的例子中使用的 `Less` 和 `Greater` 结构体[^4]。
#### 主要方法说明
- **push(element)**:向队列中添加新元素。
- **pop()**:移除当前具有最高优先权的那个元素(即堆顶)。
- **top()**:返回但不移除最前面那个拥有最高优先级别的元素。
- **empty()**:判断队列是否为空。
- **size()**:获得队列内的元素数量。
以上便是关于 C++ 如何实现和使用优先级队列的一个简单介绍[^3]。
阅读全文
相关推荐



















