欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

优先队列

程序员文章站 2022-03-06 08:08:02
...

一、默认优先级

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

例如:

#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

相关标签: 优先队列