priority_queue 的常见用法详解

admin管理员组

文章数量:1623792

1，priority_queue 又称为优先队列，其底层是用堆来进行实现的。在优先队列中，队首元素一定是当前队列中优先级最高的那一个。

当然，可以在任何时候往优先队列里面加入元素，而优先队列底层的数据结构堆（heap）会随时调整结构，使得每次的队首元素都是优先级最高的，话不多说让我们一起来了解一下吧。

2.priority_queue 的定义

    要使用优先队列，应先添加头文件 #include<queue> ,并在头文件下面加上“using namespace std;”。

其定义的写法和其他STL容器相同， typename 可以是任意基本数据类型或容器：

priority_queue<typename> name;

3.priority_queue 容器内容器的访问

        和队列不同的是优先队列没有 front()函数与back()函数，而只能通过 top() 函数来访问队首元素（也称堆顶元素），也就是优先级最高的元素。

这里引入 priority_queue 常用函数 push(), top() ,pop(), empty(), q.size()的用法：

#include<iostream>
#include<queue>
using namespace std;
int main()
{
	priority_queue<int> q;
	q.push(3);     //入队 
	q.push(5);
	q.push(1);
	cout<<q.top()<<endl;     //获取队首元素 
	q.pop();			//令队首元素出队 
	cout<<q.top()<<endl;
	if(q.empty())
	{
		cout<<"Empty"<<endl;
	}
	else
	{
		cout<<"Not empty"<<endl;
	}
	cout<<q.size()<<endl; 
	return 0;
}

 4.priority_queue 内元素优先级的设置：

优先队列最为强大的是它的排序功能，如何定义队列的优先级是运用好优先队列的关键，下面分别介绍基本数据类型（例如：int char double）与结构体类型的优先级设置的方法。

1）基本数据类型的优先级设置：（即可以直接使用的数据类型），优先队列对他们的优先级设置一般是数字越大的优先级越高，因此队首是优先级最大的那个（如果是 char 类型，则是字典序最大的）。以 int 型为例下面两种是等价的：

priority_queue<int>q;

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

可以发现第二种定义方式的尖括号内多出了两个参数：其中 vector<int>填写的是承载底层数据结构堆 （heap）的容器，如果是其他类型 可写为 vector<char>或vector<char>;

第三个参数 less<int> 则是对第一个参数的比较类，！！less<int> 表示数字大的优先级越大，而 greater<int> 表示数字小的优先级越大。 

#include<iostream>
#include<queue>
using namespace std;
int main()
{
	priority_queue<int,vector<int>,greater<int> > q;
	q.push(3);     //入队 
	q.push(5);
	q.push(1);
	cout<<q.top()<<endl;     //获取队首元素 
	return 0;
}

 2）结构体的优先级设置：

// 使用friend其排序与sort排序刚好相反 
struct node
{
	string name;
	int price;
	//friend bool operator<(const node &f1,const node &f2) 
	//建议使用上面的引用来提高效率 
	friend bool operator<(node f1,node f2)
	{
		return f1.price<f2.price;
	}
};
priority_queue<node> q;
// 不使用 friend 友元将它写在外面 
struct node
{
	string name;
	int price;
};
struct cmp
{
	bool operator() (node f1,node f2)
	{
		return f1.price>f2.price;
	}
 } 
priority_queue<node,vector<node>,cmp>;

首先对某一对象建立结构体，现在希望价格高的优先级高，就需要重载（overload）小于号“<”.重载是指对已有的运算符进行重新定义。

可以看到，node 结构体中增加了一个函数，其中“friend”为友元，后面的"bool operator<(node f1,node f2) " 这里是对小于号进行了重载事实上也仅仅只能对小于号进行重载，重载大于号会编译错误，因为从数学上来讲只需要重载小于号即 f1>f2<==>f2<f1,而我们发现 return f1.price<f2.price ,重载后小于号还是小于号的作用，因此就可一直接定义 node 类型的优先队列，其内部就是以价格高的水果为优先级高，因此可以直接定义为：

priority_queue<node> q; 

5.priority_queue的常见用途：

priority_queue 可以解决一些贪心问题，也可以对 Dijkstra 算法进行优化。

需要要注意使用 top() 函数之前，必须用 empty() 判断优先队列是否为空。 

本文标签： 详解常见priorityqueue