C++priority_queue的⽤法（含⾃定义排序⽅式）
priority_queue本质是⼀个堆。
1. 头⽂件是#include<queue>
2. 关于priority_queue中元素的⽐较
模板申明带3个参数：priority_queue<Type, Container, Functional>，其中Type 为数据类型，Container为保存数据的容器，Functional 为元素⽐较⽅式。 Container必须是⽤数组实现的容器，⽐如vector,deque等等，但不能⽤ list。STL⾥⾯默认⽤的是vector。
2.1 ⽐较⽅式默认⽤operator<，所以如果把后⾯2个参数缺省的话，优先队列就是⼤顶堆（降序），队头元素最⼤。特别注意pair的⽐较函数。
以下代码返回⼀个降序输出：
1 #include <iostream>
2 #include <queue>
3 using namespace std;
4 int main(){
5 priority_queue<int> q;
6 for( int i= 0; i< 10; ++i ) q.push(i);
7 while( !q.empty() ){
8 cout<&p()<<endl;
9 q.pop();
10 }
11 return 0;
12 }空想家
以下代代码返回pair的⽐较结果，先按照pair的first元素降序，first元素相等时，再按照cond元素降序：
1 #include<iostream>
2 #include<vector>
3 #include<queue>
天津儿童教育4 using namespace std;
5 int main(){
6 priority_queue<pair<int,int> > coll;
7 pair<int,int> a(3,4);
8 pair<int,int> b(3,5);
9 pair<int,int> c(4,3);
10 coll.push(c);
11 coll.push(b);
12 coll.push(a);
13 while(!pty())
14 {
15 cout<&p().first<<"\t"<&p().cond<<endl;
16 coll.pop();
17 }
18 return 0;
19 }
2.2 如果要⽤到⼩顶堆，则⼀般要把模板的3个参数都带进去。STL⾥⾯定义了⼀个仿函数greater<>，基本类型可以⽤这个仿函数声明⼩顶堆。
以下代码返回⼀个升序输出：
1 #include <iostream>
2 #include <queue>
3 using namespace std;
4 int main(){
5 priority_queue<int, vector<int>, greater<int> > q;
6 for( int i= 0; i< 10; ++i ) q.push(10-i);
7 while( !q.empty() ){
列夫托尔斯泰的资料
8 cout << q.top() << endl;
9 q.pop();
10 }
11 return 0;
12 }
以下代代码返回pair的⽐较结果，先按照pair的first元素升序，first元素相等时，再按照cond元素升序：
1 #include<iostream>
2 #include<vector>
3 #include<queue>
4 using namespace std;
5 int main(){
6 priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > coll;
imak7 pair<int,int> a(3,4);
8 pair<int,int> b(3,5);
9 pair<int,int> c(4,3);
10 coll.push(c);
11 coll.push(b);
海伦从零开始学英语
12 coll.push(a);
13 while(!pty())
14 {
15 cout<&p().first<<"\t"<&p().cond<<endl;
16 coll.pop();
17 }
bull shit
18 return 0;
19 }
2.3 对于⾃定义类型，则必须重载operator<；或者重写仿函数。
2.3.1 重载operator<；的例⼦：返回true时，说明左边形参的优先级低于右边形参
1 #include <iostream>
2 #include <queue>
3 using namespace std;
考研红宝书4 struct Node{
5 int x, y;
6 Node(int a=0, int b=0):
7 x(a),y(b){}
8 };
9 bool operator<(Node a, Node b){//返回true时，说明a的优先级低于b
10 //x值较⼤的Node优先级低（x⼩的Node排在队前）
11 //x相等时，y⼤的优先级低（y⼩的Node排在队前）
12 if( a.x== b.x ) return a.y> b.y;
13 return a.x> b.x;
14 }
15 int main(){
全国一卷数学16 priority_queue<Node> q;
17 for( int i= 0; i< 10; ++i )
18 q.push( Node( rand(), rand() ) );
19 while( !q.empty() ){
20 cout << q.top().x << ' ' << q.top().y << endl;
21 q.pop();
22 }
23 return 0;
24 }
⾃定义类型重载operator<；后，声明对象时就可以只带⼀个模板参数。
但此时不能像基本类型这样声明priority_queue<Node,vector<Node>,greater<Node> >，原因是greater<Node>没有定义，如果想⽤这种⽅法定义则可以重载operator >。例⼦：返回的是⼩顶堆。但不怎么⽤，习惯是重载operator<。
1 #include <iostream>
2 #include <queue>
3 using namespace std;
4 struct Node{
5 int x, y;
6 Node( int a= 0, int b= 0 ):
7 x(a), y(b) {}
8 };
9 bool operator>( Node a, Node b ){//返回true，a的优先级⼤于b
10 //x⼤的排在队前部；x相同时，y⼤的排在队前部
11 if( a.x== b.x ) return a.y> b.y;
12 return a.x> b.x;新年快乐英语怎么写
达内it培训
13 }
14 int main(){
15 priority_queue<Node,vector<Node>,greater<Node> > q;
16 for( int i= 0; i< 10; ++i )
17 q.push( Node( rand(), rand() ) );
18 while( !q.empty() ){
19 cout << q.top().x << ' ' << q.top().y << endl;
20 q.pop();
21 }
22 return 0;
23 }
2.3.2 重写仿函数的例⼦（返回值排序与2.3.1相同，都是⼩顶堆。先按x升序，x相等时，再按y升序）：
1 #include <iostream>
2 #include <queue>
3 using namespace std;
4 struct Node{
5 int x, y;
6 Node( int a= 0, int b= 0 ):
7 x(a), y(b) {}
8 };
9 struct cmp{
10 bool operator() ( Node a, Node b ){//默认是less函数
11 //返回true时，a的优先级低于b的优先级（a排在b的后⾯）
12 if( a.x== b.x ) return a.y> b.y;
13 return a.x> b.x; }
14 };
15 int main(){
16 priority_queue<Node, vector<Node>, cmp> q;
17 for( int i= 0; i< 10; ++i )
18 q.push( Node( rand(), rand() ) );
19 while( !q.empty() ){
20 cout << q.top().x << ' ' << q.top().y << endl;
21 q.pop();
22 }
23 return 0;
24 }
