优先队列(priority_queue)
优先队列可以用来存储具有优先级的元素,队头的元素都是当前队列中优先级最高(或最低)的元素
STL中的优先队列默认为最大堆,即优先级最高的先出队
结构
优先队列仅维护堆顶(top),其余元素优先级都比堆顶小
初始化
优先队列使用需要引入头文件queue
如下代码可以声明一个优先队列,其中T为数据类型,优先队列中的数据数据类型都相同
注意:使用结构体时,需要重载小于号或声明一个比较类并重载()运算符
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
| #include <bits\stdc++.h> using namespace std; struct node{ int x, y; bool operator < (const node &u)const{ return x == u.x? y<u.y : x<u.x; } };
struct cmp{ bool operator ()(const int &u, const int &v)const{ return u>v; } };
int main(){
priority_queue<T> pque; priority_queue<int, vector<int>, greater<int>> pque; }
|
基本操作
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| cout << pque.top() << endl;
pque.push(1);
pque.pop();
cout << pque.size() << endl;
cout << pque.empty() << endl;
int x = pque.top(); pque.pop(); pque.push(x+1);
|
注意:priority_queue没有迭代器,不能用begin(),end(),auto等遍历,也不能直接修改队列中的元素