优先队列是队列的一种，不过它可以按照自定义的一种方式（数据的优先级）来对队列中的数据进行动态的排序
每次的push和pop操作，队列都会动态的调整，以达到我们预期的方式来存储。
例如：我们常用的操作就是对数据排序，优先队列默认的是数据大的优先级高
所以我们无论按照什么顺序push一堆数，最终在队列里总是top出最大的元素。
优先队列的常用操作
优先级队列支持的操作q.empty() 如果队列为空，则返回true，否则返回false
q.size() 返回队列中元素的个数
q.pop() 删除队首元素，但不返回其值
q.top() 返回具有最高优先级的元素值，但不删除该元素
q.push(item) 在基于优先级的适当位置插入新元素
用法：
示例：将元素5，3，2，4，6依次push到优先队列中，print其输出。
1. 标准库默认使用元素类型的<操作符来确定它们之间的优先级关系。
priority_queue<int> pq;通过<操作符可知在整数中元素大的优先级高。 故示例1中输出结果为： 6 5 4 3 2
2. 数据越小，优先级越高
priority_queue<int, vector<int>, greater<int> >pq;其中 第二个参数为容器类型。 第二个参数为比较函数。 故示例2中输出结果为：2 3 4 5 6
3. 自定义优先级，重载比较符号
重载默认的 < 符号
struct node { friend bool operator< (node n1, node n2) { return n1.priority < n2.priority; } int priority; int value; };这时，需要为每个元素自定义一个优先级。
注：重载>号会编译出错，因为标准库默认使用元素类型的<操作符来确定它们之间的优先级关系。 而且自定义类型的<操作符与>操作符并无直接联系
#include<iostream> #include<functional> #include<queue> using Namespace stdnamespace std; struct node { friend bool operator< (node n1, node n2) { return n1.priority < n2.priority; } int priority; int value; }; int main() { const int len = 5; int i; int a[len] = {3,5,9,6,2}; //示例1 priority_queue<int> qi; for(i = 0; i < len; i++) qi.push(a[i]); for(i = 0; i < len; i++) { cout<<qi.top()<<" "; qi.pop(); } cout<<endl; //示例2 priority_queue<int, vector<int>, greater<int> >qi2; for(i = 0; i < len; i++) qi2.push(a[i]); for(i = 0; i < len; i++) { cout<<qi2.top()<<" "; qi2.pop(); } cout<<endl; //示例3 priority_queue<node> qn; node b[len]; b[0].priority = 6; b[0].value = 1; b[1].priority = 9; b[1].value = 5; b[2].priority = 2; b[2].value = 3; b[3].priority = 8; b[3].value = 2; b[4].priority = 1; b[4].value = 4; for(i = 0; i < len; i++) qn.push(b[i]); cout<<"优先级"<<'\t'<<"值"<<endl; for(i = 0; i < len; i++) { cout<<qn.top().priority<<'\t'<<qn.top().value<<endl; qn.pop(); } return 0; } 先级队列可以用向量(vector)或双向队列(deque)来实现(注意list container 不能用来实现queue，因为list 的迭代器不是任意存取iterator，而pop 中用到堆排序时是要求randomaccess iterator 的!)： priority_queue<vector<int>, less<int>> pq1; // 使用递增less<int>函数对象排序 priority_queue<deque<int>, greater<int>> pq2; // 使用递减greater<int>函数对象排序 其成员函数有“判空(empty)” 、“尺寸(Size)” 、“栈顶元素(top)” 、“压栈(push)” 、“弹栈(pop)”等。 例： 1 #include < iostream > 2 #include < queue > 3 using namespace std; 4 5 class T { 6 public : 7 int x, y, z; 8 T( int a, int b, int c):x(a), y(b), z(c) 9 { 10 } 11 }; 12 bool operator < ( const T & t1, const T & t2) 13 { 14 return t1.z < t2.z; // 按照z的顺序来决定t1和t2的顺序 15 } 16 main() 17 { 18 priority_queue < T > q; 19 q.push(T( 4 , 4 , 3 )); 20 q.push(T( 2 , 2 , 5 )); 21 q.push(T( 1 , 5 , 4 )); 22 q.push(T( 3 , 3 , 6 )); 23 while ( ! q.empty()) 24 { 25 T t = q.top(); 26 q.pop(); 27 cout << t.x << " " << t.y << " " << t.z << endl; 28 } 29 return 1 ; 30 } 输出结果为(注意是按照z的顺序从大到小出队的)： 3 3 6 2 2 5 1 5 4 4 4 3 再看一个按照z的顺序从小到大出队的例子： 1 #include < iostream > 2 #include < queue > 3 using namespace std; 4 class T 5 { 6 public : 7 int x, y, z; 8 T( int a, int b, int c):x(a), y(b), z(c) 9 { 10 } 11 }; 12 bool operator > ( const T & t1, const T & t2) 13 { 14 return t1.z > t2.z; 15 } 16 main() 17 { 18 priority_queue < T, vector < T > , greater < T > > q; 19 q.push(T( 4 , 4 , 3 )); 20 q.push(T( 2 , 2 , 5 )); 21 q.push(T( 1 , 5 , 4 )); 22 q.push(T( 3 , 3 , 6 )); 23 while ( ! q.empty()) 24 { 25 T t = q.top(); 26 q.pop(); 27 cout << t.x << " " << t.y << " " << t.z << endl; 28 } 29 return 1 ; 30 } 输出结果为： 4 4 3 1 5 4 2 2 5 3 3 6 如果我们把第一个例子中的比较运算符重载为： bool operator < (const T &t1, const T &t2) { return t1.z > t2.z; // 按照z的顺序来决定t1和t2的顺序} 则第一个例子的程序会得到和第二个例子的程序相同的输出结果。