在 C++ 中,priority_queue
(优先队列)是一种容器适配器,它提供了一种按照优先级自动排序的队列功能。与普通队列(queue
)的“先进先出(FIFO)”不同,priority_queue
中每次出队的元素都是当前队列中优先级最高的元素。
核心特性
- 默认排序:默认情况下,
priority_queue
采用大顶堆(max-heap) 结构,即每次出队的是最大的元素(数值越大优先级越高)。 - 底层容器:默认基于
vector
实现(也可指定为deque
),通过堆算法维护元素的优先级顺序。 - 不可直接访问中间元素:只能访问队顶(优先级最高)的元素,不支持迭代器遍历。
头文件与定义
使用 priority_queue
需要包含头文件 <queue>
,定义格式如下:
#include <queue>
using namespace std;// 默认:大顶堆(元素类型为 T,底层容器为 vector,比较器为 less<T>)
priority_queue<T> pq;// 自定义:指定底层容器和比较器(例如小顶堆)
priority_queue<T, Container, Compare> pq;
常用操作
操作 | 功能说明 | 时间复杂度 |
---|---|---|
pq.push(val) |
插入元素 val 到队列,并维护优先级 |
O(log n) |
pq.pop() |
移除队顶(优先级最高)的元素 | O(log n) |
pq.top() |
返回队顶元素的引用(不删除) | O(1) |
pq.empty() |
判断队列是否为空(空返回 true ) |
O(1) |
pq.size() |
返回队列中元素的个数 | O(1) |
示例:默认大顶堆
#include <iostream>
#include <queue>
using namespace std;int main() {priority_queue<int> pq;// 插入元素pq.push(30);pq.push(10);pq.push(50);pq.push(20);// 输出队顶并移除,直到为空while (!pq.empty()) {cout << pq.top() << " "; // 每次输出当前最大元素pq.pop();}// 输出:50 30 20 10return 0;
}
自定义优先级(小顶堆)
如果需要小顶堆(每次出队最小元素),可以通过指定比较器 greater<T>
实现:
#include <iostream>
#include <queue>
#include <vector> // 需显式指定底层容器
using namespace std;int main() {// 小顶堆:元素类型 int,底层容器 vector,比较器 greater<int>priority_queue<int, vector<int>, greater<int>> pq;pq.push(30);pq.push(10);pq.push(50);pq.push(20);while (!pq.empty()) {cout << pq.top() << " "; // 每次输出当前最小元素pq.pop();}// 输出:10 20 30 50return 0;
}
自定义类型的优先级
对于自定义结构体/类,需要通过重载运算符或自定义比较器指定优先级:
方法1:重载 <
运算符(用于默认大顶堆)
#include <iostream>
#include <queue>
using namespace std;struct Person {string name;int age;// 重载 <:年龄大的优先级高(用于大顶堆)bool operator<(const Person& other) const {return age < other.age; // 注意:堆内部用 < 比较,返回 true 表示当前对象优先级低}
};int main() {priority_queue<Person> pq;pq.push({"Alice", 25});pq.push({"Bob", 30});pq.push({"Charlie", 20});while (!pq.empty()) {cout << pq.top().name << "(" << pq.top().age << "), ";pq.pop();}// 输出:Bob(30), Alice(25), Charlie(20),return 0;
}
方法2:自定义比较器(灵活控制优先级)
#include <iostream>
#include <queue>
#include <vector>
using namespace std;struct Person {string name;int age;
};// 自定义比较器:年龄小的优先级高(用于小顶堆)
struct CompareAge {bool operator()(const Person& a, const Person& b) {return a.age > b.age; // 注意:返回 true 表示 a 优先级低于 b}
};int main() {priority_queue<Person, vector<Person>, CompareAge> pq;pq.push({"Alice", 25});pq.push({"Bob", 30});pq.push({"Charlie", 20});while (!pq.empty()) {cout << pq.top().name << "(" << pq.top().age << "), ";pq.pop();}// 输出:Charlie(20), Alice(25), Bob(30),return 0;
}
总结
priority_queue
适用于需要动态获取最大/最小元素的场景(如任务调度、贪心算法等)。- 默认是大顶堆,通过
greater<T>
可改为小顶堆。 - 自定义类型需通过重载运算符或比较器指定优先级规则。
- 不支持随机访问,仅能操作队顶元素,插入和删除的时间复杂度为 O(log n)。
在 C++ 中,priority_queue
(优先队列)和 queue
(普通队列)都是容器适配器,但它们的核心行为和应用场景有显著区别,主要体现在元素的访问和移除顺序上。
1. 核心特性对比
特性 | queue (普通队列) |
priority_queue (优先队列) |
---|---|---|
元素顺序规则 | 遵循“先进先出(FIFO)”原则:先插入的元素先被移除。 | 遵循“优先级最高先出”原则:每次移除的是当前队列中优先级最高的元素(与插入顺序无关)。 |
底层数据结构 | 默认基于 deque 实现(也可指定 list )。 |
默认基于 vector 实现(也可指定 deque ),内部通过堆算法维护优先级。 |
访问权限 | 只能访问队头(front)和队尾(back)元素。 | 只能访问优先级最高的元素(队顶,top),无法直接访问其他元素(包括队尾)。 |
典型应用场景 | 需按插入顺序处理元素的场景(如广度优先搜索 BFS、缓存队列、任务排队等)。 | 需动态获取“最大/最小元素”的场景(如贪心算法、任务调度、TOP-K 问题等)。 |
2. 操作上的差异
两者的基本操作(push
、pop
、empty
、size
)名称相同,但行为逻辑不同:
-
push
操作:queue
:将元素插入队尾,不改变其他元素顺序。priority_queue
:将元素插入后,会通过堆调整重新排序,确保队顶始终是优先级最高的元素。
-
pop
操作:queue
:移除队头(最先插入的元素)。priority_queue
:移除队顶(当前优先级最高的元素),并重新调整堆结构维持优先级。
-
元素访问:
queue
用front()
获取队头元素,back()
获取队尾元素。priority_queue
只能用top()
获取优先级最高的元素(无front
或back
)。
3. 示例对比
普通队列(queue
)示例
#include <iostream>
#include <queue>
using namespace std;int main() {queue<int> q;q.push(3); // 队尾:3q.push(1); // 队尾:1(队列:3, 1)q.push(2); // 队尾:2(队列:3, 1, 2)while (!q.empty()) {cout << q.front() << " "; // 依次输出队头(先入先出)q.pop();}// 输出:3 1 2return 0;
}
优先队列(priority_queue
)示例
#include <iostream>
#include <queue>
using namespace std;int main() {priority_queue<int> pq; // 默认大顶堆(最大值优先)pq.push(3);pq.push(1);pq.push(2);while (!pq.empty()) {cout << pq.top() << " "; // 依次输出优先级最高的元素(最大的)pq.pop();}// 输出:3 2 1return 0;
}
4. 总结
queue
是“顺序依赖”的容器,适合按插入顺序处理元素,核心是FIFO。priority_queue
是“优先级依赖”的容器,适合需要动态获取最值的场景,核心是优先级排序。- 两者均不支持随机访问,只能通过特定接口(
front
/top
)访问特定元素,且插入/删除操作的时间复杂度不同(queue
为 O(1),priority_queue
为 O(log n))。