【数据结构】优先队列

优先队列(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;
    // 声明一个小顶堆,传入仿函数, 第二个参数表示优先队列底层储存容器为vector
    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等遍历，也不能直接修改队列中的元素