STL库--priority

STL库--priority_queue

priority_queue定义

prority_queue容器内元素的访问

priority_queue()常用函数实例解析

priority_queue内元素优先级的设置

priority_queue的常见用途

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

桃子（优先级3）
梨子（优先级4）
苹果（优先级1）

那么出队的顺序为梨子（4）、桃子（3）、苹果（1）

当然，可以在任何时候往优先队列里面加入元素，而优先队列底层的数据结构堆会随时调整结构，使得每次的队首元素都是优先级最大的。关于这里的优先级则是规定出来的。

priority_queue定义

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

prioroty_queue<typename> name;

prority_queue容器内元素的访问

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

#include<stdio.h>
#include<queue>
using namespace std;
int main(){
	priority_queue<int> q;
	q.push(3);
	q.push(4);
	q.push(1);
	printf("%d\n",q.top());
	return 0;
}

输出结果

priority_queue()常用函数实例解析

（1）push()

push(x)将令x入队，时间复杂度为 $O\left ( logN \right )$ ，其中N为当前优先队列中的元素个数

（2）top()

top()可以获得队首元素，时间复杂度为 $O\left ( 1 \right )$

（3）pop()

pop()令队首元素出队，时间复杂度为 $O\left ( logN \right )$ ，其中N为当前优先队列中的元素个数。

#include<stdio.h>
#include<queue>
using namespace std;
int main(){
	priority_queue<int> q;
	q.push(3);
	q.push(4);
	q.push(1);
	printf("%d\n",q.top());
	q.pop();
	printf("%d\n",q.top());
	return 0;
}

输出结果

4
3

（4）empty()

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

#include<stdio.h>
#include<queue>
using namespace std;
int main(){
	priority_queue<int> q;
	if(q.empty()==true){
		printf("Empty\n");
	}
	else{
		printf("Not Empty\n");
	}
	q.push(1);
	if(q.empty()==true){
		printf("Empty\n");
	}
	else{
		printf("Not Empty\n");
	}
	return 0;
}

（5）size()

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

#include<stdio.h>
#include<queue>
using namespace std;
int main(){
	priority_queue<int> q;
	q.push(3);
	q.push(4);
	q.push(1);
	printf("%d\n",q.size());
	return 0;
}

priority_queue内元素优先级的设置

如何定义优先队列内元素的优先级是运用好优先队列的关键，下面分别介绍基本数据类型与结构体类型的优先级设置方法。

（1）基本数据类型的优先级设置

此处指的基本数据类型就是int型，double型，char型等可以直接使用的数据类型，优先队列对它们的优先级设置一般是数字大的优先级越高，因此队首元素就是优先队列内的元素最大的那个（如果char型，则是字典序最大的）。对基本数据类型来说，下面两种优先队列的定义是等价的（以int型为例）

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

可以发现，第二种定义方式的尖括号多出了两个参数：一个是vector<int>，另一个是less<int>。其中vector<int>填写的是来承载底层数据结构堆的容器，如果第一个参数是double型或char型，则此处只需要填写vector<double>或vector<char>；而第三个参数less<int>则是对第一个参数的比较类，less<int>表示数字大的优先级越大，而greater<int>表示数字小的优先级越大。

因此，如果想让优先队列总是把最小的元素放在队首，只需进行如下定义：

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

#include<stdio.h>
#include<queue>
using namespace std;
int main(){
	priority_queue<int,vector<int>,greater<int> > q;
	q.push(3);
	q.push(4);
	q.push(1);
	printf("%d\n",q.top());
	return 0;
}

输出结果

事实上，即便是基本数据类型，也可以使用下面的结构体的优先级设置方法，只不过第三个参数的写法不太一样。

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

可以举一个水果的例子，对水果的价格和名称建立一个结构体

struct fruit{
	string name;
	int price;
};

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

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

可以看到，fruit结构体增加了一个函数，其中”friend"为友元，后面的”bool operator < (fruit f1,fruit f2)"对fruit类型的操作符“<"进行了重载（重载大于号会编译错误，因为从数学上来说只需要重载小于号，即f1>f2等价于判断f2<f1，而f1==f2等价于判断!(f1<f2)&&!(f2<f1)，函数内部为"return f1.price<f2.price"，因此重载后小于号还是小于号的作用。此时就可以直接定义fruit类型的优先队列，其内部就是以价格高的水果为优先级高。

priority_queue<fruit> q;

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

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

完整代码如下：

#include<iostream>
#include<string>
#include<queue>
using namespace std;
struct fruit{
	string name;
	int price;
	friend bool operator < (fruit f1,fruit f2){
		return f1.price > f2.price;
	}
}f1,f2,f3;
int main(){
	priority_queue<fruit> q;
	f1.name="桃子";
	f1.price=3;
	f2.name="梨子";
	f2.price=4;
	f3.name="苹果";
	f3.price=1;
	q.push(f1);
	q.push(f2);
	q.push(f3);
	cout<<q.top().name<<" "<<q.top().price<<endl;
	return 0;
}

输出结果

苹果 1

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

或者也可以把结构体定义在外面，只需要把friend去掉，把小于号改成一对小括号，然后把重载的函数写在结构体外面，同时将其用struct包装起来。

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

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

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

完整代码如下：

#include<iostream>
#include<string>
#include<queue>
using namespace std;
struct fruit{
	string name;
	int price;
}f1,f2,f3;
struct cmp{
	bool operator () (fruit f1,fruit f2){
		return f1.price > f2.price;
	}
};
int main(){
	priority_queue<fruit,vector<fruit>,cmp> q;
	f1.name="桃子";
	f1.price=3;
	f2.name="梨子";
	f2.price=4;
	f3.name="苹果";
	f3.price=1;
	q.push(f1);
	q.push(f2);
	q.push(f3);
	cout<<q.top().name<<" "<<q.top().price<<endl;
	return 0;
}

当然即便是基本数据类型或者其他STL容器，也可以通过同样的方式来定义优先级。

最后指出，如果结构体内的数据较为庞大（例如出现了字符串或者数组），建议使用引用来提高效率，此时比较类的参数需要加上"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;
}