优先队列

一、默认优先级

我们知道了队列是先进先出，那么优先队列则不一样了，进的顺序不能决定出的顺序，优先队列出的顺序是按照自己设置的优先等级来出队列的，如果自己不设置优先级的话，默认优先级为越大优先级越高。

例如：

#include <iostream>
#include <queue>
using namespace std;
priority_queue<int>que;
int main()
{
	que.push(1);
	que.push(3);
	que.push(5);
	que.push(4);
	que.push(2);
	while(!que.empty())
	{
		cout<<que.top()<<endl;
		que.pop();
	}
	return 0;
	
}
//输出结果为5、4、3、2、1

二、优先级的设置

我们知道既然默认的优先级是越大优先级越高，那么我们如何来更改这个优先级呢？

1、int型

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

测试代码如下：

#include <iostream>
#include <queue>//所需头文件 
#include <vector>//所需头文件 
using namespace std;
int main()
{
	priority_queue<int,vector<int>,less<int> >que1;//输出结果从大到小排序 
	priority_queue<int,vector<int>,greater<int> >que2;//输出结果从小到大排序 
	que1.push(1);
	que1.push(5);
	que1.push(3);
	que1.push(2);
	que1.push(4);
	que2.push(1);
	que2.push(5);
	que2.push(3);
	que2.push(2);
	que2.push(4);
	cout<<"que1: ";
	while(!que1.empty())
	{
		cout<<que1.top()<<" ";
		que1.pop();
	}
	cout<<endl;
	cout<<"que2: ";
	while(!que2.empty())
	{
		cout<<que2.top()<<" ";
		que2.pop();
	}
	cout<<endl;
	return 0;
}
/*输出结果为：que1: 5 4 3 2 1 
            que2: 5 4 3 2 1
*/ 

2、结构体型（和sort结构体排序的cmp类似）

struct node
{
int c,d;
};
bool operator <( const node & a, const node & b)//重载运算符
{
if(a.c==b.c) return a.d<b.d;
return a.c<b.c;
}
priority_queue <node > que ;

测试代码：

#include <iostream>
#include <queue>
using namespace std;
struct node
{
	int n,m;
	friend bool operator< (const node &a,const node &b)
	{
		if(a.m!=b.m) return a.m>b.m;//若m不相同，则m小的放在前面（与正常逻辑相反）
		return a.n<b.n;//若m相同，则n大的放在前面（与正常逻辑相反） 
	} 
}N[1000];
int main()
{
	priority_queue<node> que;
	for(int i=0;i<6;i++)
	{
		cin>>N[i].n>>N[i].m;
		que.push(N[i]);
	}
	while(!que.empty())
	{
		cout<<"n: "<<que.top().n<<" m: "<<que.top().m<<endl;//先进先出
		que.pop(); 
	}
	while(!que.empty()) que.pop();//清空 
	return 0;
}

运行结果：

关于结构体优先级的设置可以参照HDU1873题 看病要排队

链接：https://blog.csdn.net/KK_2018/article/details/81259019