优先队列

详细看这个视频：BV1P64y1h7dk

  • 引入头文件

  • 定义

    priority_queue <int> que;

    priority_queue <int, vector<int>,less<int>> que;

    • 内部元素类型int

    • 使用容器vector

    • 比较方法less大顶堆，greater小顶堆

    • 对象名字que

    • 默认最大堆

  • 操作

    • que.size()优先队列元素数量
    • que.push(x)向优先队列插入元素x
    • que.pop()删除优先级最高的元素
    • que.top()访问优先级最高的元素，堆顶元素
    • que.empty()判断堆是否为空
1
2
3
4
5
6
7
8
9
10
11
#include <queue>
...
	priority_queue<int> que;
	que.push(7);
	que.push(1);
	que.push(5);
	while(!que.empty()){
		cout<<que.top()<<"";
		que.pop();
	}
	cout<<endl;
  • 自定义类型放入优先队列
1
2
3
4
5
6
7
8
9
10
struct node{
	int x,y;
	//运算符重载，定义比较规则，只能重载<
	bool operator < (const node &b) const{
		return this->x < b.x;
		//<小顶堆，>大顶堆
	}
}
priority_queue <node> que;
que.push((node){1,5});