C++priority_queue容器使用

前言

在图搜索时经常 用到宽搜来求得最短路，而有这样一类题目在求得最短路时又要使得 花费(cost可以是任意一种要求，比如改变方向的次数或者其他)最小 ，这样每次队列中出队的元素就要满足元素优先出队。STL中的 priority_queue(优先队列) 就可以解决这样的问题。这样的模板类在头文件中，内部实现是 堆。

使用细节

优先队列与队列的差别在于优先队列不是按 照入队的顺序出队，而是按照队列中元素的优先权顺序出队（默认为大者优先， 也可以通过指定算子来指定自己的优先顺序）。
priority_queue模板类有三个模板参数，第一个是元素类型，第二个容器 类型，第三个是比较算子。其中后两个都可以省略，默认容器为vector，默 认算子为less，即小的往前排，大的往后排（出队时序列尾的元素出队）。

定义priority_queue对象的示例代码如下： 
priority_queue<int> q1; 
priority_queue< pair<int, int> > q2;  // 注意在两个尖括号之间 一定要留空格。 
priority_queue<int, vector<int>, greater<int> > q3; // 定义小的先出队 

对于比较算子:

如果是基本数据类型，或已定义了比较运算符的类，可以直接用STL的less 算子和greater算子——默认为使用less算子，即小的往前排，大的先出队。
如果要定义自己的比较算子，方法有多种，这里介绍其中的一种：重载比较运 算符。优先队列试图将两个元素x和y代入比较运算符(对less算子，调用 x<y，对greater算子，调用x>y)，若结果为真，则x排在y前面，y将先 于x出队，反之，则将y排在x前面，x将先出队。
简而言之就是：对于less重载<运算符，判断为true，将大的那方先出队

---

测试代码

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <string>
#include <deque>
#include <queue>
#include <set>
#include <map>
#include <list>
#include <stack>
#include <vector>
#include <utility>
using namespace std;

struct Test01 {
	int x,y,z;
public:
	Test01 () {
		x = 1;
		y = 1;
		z = 1;
	}
	
	Test01 (int x, int y, int z) {
		this->x = x;
		this->y = y;
		this->z = z;
	}
	
	~Test01(){};
	
	bool operator < (const Test01 &A) const{  //如果为true就让大的那一方先出队
		if(this->z == A.z) {
			if(this->y == A.y) {
				return this->x < A.x;
			}
			return this->y < A.y;
		}
		return this->z < A.z;
	}
	
	friend bool operator > (Test01 A, Test01 B) {  //类似调用外部函数，不能有this，因为不知道是哪个的
		if(B.z == A.z) {
			if(B.y == A.y) {
				return B.x < A.x;
			}
			return B.y < A.y;
		}
		return B.z < A.z;
	}
};

int main() {
	int T;
	priority_queue<Test01, vector<Test01>, less<Test01> > pq;
	//这里如果要重载比较算子的话要连同容器也一起写，否则报错  less默认，可以不写
	pq.push(Test01());
	pq.push(Test01(1,2,3));
	pq.push(Test01(1,1,3));
	pq.push(Test01(0,1,3));
	while(!pq.empty()) {
		Test01 tmp = pq.top();
		pq.pop();
		cout<< tmp.x << " " << tmp.y << " " << tmp.z << endl;
	}
	
	cout<<endl;
	
	priority_queue<Test01, vector<Test01>, greater<Test01> > pq2;
	//这里如果要重载比较算子的话要连同容器也一起写，否则报错
	pq2.push(Test01());
	pq2.push(Test01(1,2,3));
	pq2.push(Test01(1,1,3));
	pq2.push(Test01(0,1,3));
	while(!pq2.empty()) {
		Test01 tmp = pq2.top();
		pq2.pop();
		cout<< tmp.x << " " << tmp.y << " " << tmp.z << endl;
	}
	return 0;
}