[C++知识库]priority_queue的一般用法

什么是优先队列

priority_queue本质是一个堆。

特点

priority_queue模拟的是队列这种数据结构，底层用堆结构来存储数据，使用该容器存储元素和队列相似，即“只从一端进（称为队尾），只从一端出（称为队首）”。我们每次访问也只能访问到队首元素。
但是优先队列存在优先级，也就是优先级高的在队列中位置更靠近队首，而队首元素也是优先队列中优先级最高的元素。
对于优先级的评定规则，我们默认为$std::less<T>$按元素值从大到小排序，我们也可以用$std::greater<T>$按元素值从小到达排序。（前者队首元素值在队列中最大，后者队首元素值在队列中最小）
我们也可以自定义优先级$operator$
可以参考一下代码

priority_queue<Type> T;
/*表示一个存储元素类型为Type类型的命名为T的优先队列，其优先级默认为less*/
等同于如下定义方式
priority_queue<Type, vector<Type> ,less<Type> >T;
而如果是优先级为greater，则如下
priority_queue<Type, vettor<Type>, greater<Type> >T;
/*表示存储元素类型为Type类型的命名为T的优先队列，优先级为greater，即从小到大排血*/

所带参数

priority_queue<Type, Container, Functional>
Type表示数据类型，Container表示为保存数据的容器，Functional即为元素比较方式。
注意： $Container$必须是用数组实现的容器，例如$vector，deque$等，但是不能用$list$。默认容器为$vector$。

相关操作

priority_queue<int> heap;//创建一个命名为heap的优先队列

heap.top()，heap.pop()，heap.empty() and heap.push()

heap.push(num);
//将num数据从队尾压入优先队列，同时队列会自行按照从大到小的顺序将其放在正确的位置
heap.pop();
//与队列相同，弹出队首的元素
heap.top();
//优先队列没有front，但是又top，该操作为返回队首的元素
heap.empty();
//如果该优先队列为空，那么返回true，否则返回false

我们看如下代码展示（后面的代码我们仅展示solve里面的部分）

#include<iostream>
#include<algorithm>
#include<queue>
#define INF 0x7fffffff
#define ll long long
#define rei register int
using namespace std;
const int N = 1e6+5;
void solve(){
	priority_queue<int>heap;
	heap.push(1);
	heap.push(2);
	heap.push(9);
	while(!heap.empty()){
		printf("%d ",heap.top());
		heap.pop();
	}
}
int main(){
	solve();
	return 0;
}

运行结果如下

我们可以看到heap里的元素按从大到小的顺序输出，我们当然也可以从小到大得输出。
如下所示

void solve(){
	priority_queue<int, vector<int>,greater<int> >heap;
	for(int i = 10;i > 0;i--){
		heap.push(i);
	}
	while(!heap.empty()){
		printf("%d ",heap.top());
		heap.pop();
	}
}

运行结果如下：

heap.size()， heap.swap()

heap.size();//返回heap中得元素个数
heap.swap(heap1);//交换两个优先队列的所有数据

注意：数据互换的两个优先队列必须存储数据相同且底层存储的容器必须相同
举个栗子如下所示

void solve(){
	priority_queue<int >heap1;
	priority_queue<int >heap2;
	for(int i = 0;i < 10;i++)heap1.push(i);
	for(int i = 11;i < 21;i++)heap2.push(i);
	printf("heap1的元素个数%d heap2的元素个数%d\n",heap1.size(),heap2.size());
	printf("交换前\n");
	for(int i = 0;i < 10;i++)printf("%d ",heap1.top()), heap1.pop();printf("\n");
	for(int i = 0;i < 10;i++)printf("%d ",heap2.top()), heap2.pop();printf("\n");
	printf("交换后\n");
	for(int i = 0;i < 10;i++)heap1.push(i);
	for(int i = 11;i < 21;i++)heap2.push(i);
	heap1.swap(heap2);
	for(int i = 0;i < 10;i++)printf("%d ",heap1.top()), heap1.pop();printf("\n");
	for(int i = 0;i < 10;i++)printf("%d ",heap2.top()), heap2.pop();printf("\n");
}

运行结果如下：

自定义operator优先级

直接代码展示更加直观一些

struct node{
	int x, y;
	node (int a = 0, int b = 0):
		x(a),y(b){}
};
struct cmp{
	bool operator()(node a, node b){
		if(a.y==b.y)return a.x > b.x;
		return a.y < b.y;
	}
};
void solve(){
	priority_queue<node, vector<node>, cmp> heap;
	node vec;
	for(int i = 0;i < 10;i++){
		heap.push(node(rand(),rand()));
	}
	while(!heap.empty()){
		printf("%d %d\n",heap.top().x,heap.top().y);
		heap.pop();
	}
}

测试结果如下

以上就是我对优先队列的一个总结，如果有不对的地方希望大家可以指正。

下面介绍一道利用优先队列来解决的练习题——畜栏预定