priority_queue的常见用法详解

前言

priority_queue又称为优先队列，其底层是用堆来进行实现的。在优先队列中，队首元素一定是当前队列中优先级最高的那一个(默认是大根堆)。
例如在队列有如下元素，且定义好了优先级:

桃子(优先级3)
梨子(优先级4)
苹果(优先级1)
那么出队的顺序为:  梨子(4)->桃子(3)->苹果(1)。

当然，可以在任何时候往优先队列里面加入(push)元素。而优先队列底层的数据结构堆(heap)会随时调整结构，
使得每次的队首元素都是优先级最大的。
关于这里的优先级是规定出来的。例如上面的例子中，也可以规定数字越小的优先级越大。

priorithy_queue的定义

要使用优先队列，需要的头文件：

#inlcude<queue>

需要的其他东西:

using namespace std;

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

priority_queue<typename>name;

priority_queue容器内元素的访问

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

priority_queue常用函数

(1)push()
push(x)将令x入队，时间复杂度为O(logN),其中N为当前优先队列中的元素个数。
(2)top()
top()可以获得队首元素(即堆顶元素)，时间复杂度为O(1)。
(3)pop()
pop()令队首元素(即堆顶元素)出队，时间复杂度为O(logN),其中N为当前优先队列中的元素个数。

(4)empty()
empty()检测优先队列是否为空，返回true则为空，返回false则为非空。时间复杂度为O(1)。

(5)size()
size()返回优先队列内元素的个数，时间复杂度为O(1)。

priority_queue内元素优先级的设置

如何定义优先级队列内元素的优先级是运用好优先队列的关键，下面分别介绍基本数据类型
(例如 int 、double、char)与结构体类型的优先级设置方法。
(1)基本数据类型的优先级设置
此处指的基本数据类型就是int型、double 型、char型等可以直接使用的数据类型，优先队列对它们的优先级设置般是数字大的优先级越高， 因此队首元索就是优先队列内元素最大的那个(如果char 型，则是字典序最大的)。
对基本数据类型来说，下面两种优先队列的定义是等价的(以int型为例，注意最后两个>之间有一个空格):

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

可以发现，第二种定义方式的尖括号内多出了两个参数：一个是vector,另一个是less.其中vector (也就是第二个参数)填写的是来承载底层数据结构堆(heap)的容器，如果第一个参数是double型或char型，则此处只需要填写vector-或vector;而第三个参数less-则是对第一个参数的比较类， less表示数字大的优先级越大，而greater表示数字小的优先级越大。
因此，如果想让优先队列总是把最小的元素放在队首，只需进行如下定义：

priority_queue<int, vector<int>, greater<int> >a;

下面是一个示例：

事实上，即便是基本数据类型，也可以使用下面讲解的结构体的优先级设置方法，只不过第三个参数的写法不太一样了。
下面看一下结构体的优先级的设置方法。
(2)结构体的优先级设置
以一个水果的名称和价格为例:

struct fruit
{
	string name;
	int price;
};

现在希望按水果的价格高的为优先级高，就需要重载( overload )小于号 " < "。重载是指对已有的运算符进行重新定义，
也就是说，可以改变小于号的功能(例如把它重载为大于号的功能)

struct fruit
{
	string name;
	int price;
	friend bool operator < (fruit f1,fruit f2)
	{
		return f1.peice<f2.price;
	}
};

priority_queue<fruit> q;

同理，如果想要以价格低的水果为优先级高，那么只需要把return 中的小于号改为大于号即可。

struct fruit
{
	string name;
	int price;
	friend bool operator < (fruit f1,fruit f2)
	{
		return f1.price > f2.price;
	}
};

读者会发现，此处对小于号的重载与排序函数sort中的cmp函数有些相似，它们的参数都是两个变量，函数内部都是return了true或者false,
事实上，这两者的作用确实是类似的只不过效果看上去似乎是“相反”的。在排序中，如果是“return f1.price > f2.price",
那么则是按价格从高到低排序，但是在优先队列中却是把价格低的放到队首。原因在于，优先队列本身默认的规则就是优先级高的放在队首，因此把小于号重载为大于号的功能时只是把这个规则反向一下。
如果读者无法理解，那么不妨记住，优先队列的这个函数与sort()中的cmp函数的效果是相反的。

那么，有没有办法跟sort() 中的cmp函数那样写在结构体外面呢? 自然是有办法的。
只需要把friend 去掉， 把小于号改成一对小括号，然后把重载的函数写在结构体外面，同时将其用
struct包装起来。

struct cmp
{
	bool operator () (fruit f1,fruit f2)
	{
		return f1.price>f2.price;
	}
};

在这种情况下，需要用之前讲解的第二种定义方式来定义优先队列:

priority_queue<fruit,vector<fruit>,cmp> q;

可以看到此处只是把greater()部分换成了cmp

即便是基本数据类型或者其他STL容器(例如 set),也可以通过同样的方式来定义优先级。
如果结构体内的数据较为庞大(例如出现了字符串或数组)，建议使用引用来提高效率。
此时比较类的参数中需要加上"const “和” &" 。

friend bool operator < (const fruit &f1,const fruit &f2)
{
	return f1.price>f2.price;
}
bool operator () (const fruit &f1, const fruit &f2)
{
	return  f1.price>f2.price; 
}

priority_queue的常见用途

priority_queue可以解决一些贪心问题，也可以对Dijkstra算法进行优化(因为优先队列的本质是堆)
有一点需要注意的是，使用pop()函数前，必须用empty()判断优先队列是否为空,否则可能因为队空而出现错误。