C++ priority_queue

priority queue在许多的特别场合还是很实用的，优先队列是依据堆（二叉树）实现的，效率是O(lgn)，因为它带来的便利，人们可以少写很多的代码，所以学习它是有必要的。

很多时候我们会自己定义比较函数，因为标准库默认使用元素类型的<操作符来确定它们之间的优先级关系，所以如果用>在g++编译器中编译不过，在函数中operator旁边还是用<吧，或者使用()。使用”priority_queue,greater >“类似的语句可以将大到小的默认顺序改成小到大（头文件是，我们也可以自己写一个比较类设定优先级。 struct cmp{    bool operator()(type a,type b){        return -------;    } };

#include#include#include#include#includeusing namespace std;struct cmp{ bool operator()(int a,int b){ return a>b; //想让其从小到大输出,return > }};struct point{ int x,y; void show(){ printf("(%d,%d)\n",x,y); }};struct cmp2{ bool operator()(point a,point b){ return (abs(a.x)+abs(a.y))<(abs(b.x)+abs(b.y)); }};int main(){ //优先队列默认按照从大到小的顺序排列输出 freopen("cout.txt","w",stdout); int a[5]={3,5,2,1,7}; priority_queue v; for( int i = 0; i < 5; i++ ) { v.push(a[i]); } cout<<"v.size:"<,greater > v2; //priority_queue,less > v; //less 降序 ,greater 升序 for( int i = 0; i < 5; i++ ) { v2.push(a[i]); } cout<<"v2 从小到大输出：\n"; while( !v2.empty() ) { cout << v2.top() << endl; v2.pop(); } priority_queue,cmp> v3; for( int i = 0; i < 5; i++ ) { v3.push(a[i]); } cout<<"自定义比较的V3输出:\n"; while( !v3.empty() ) { cout << v3.top() << endl; v3.pop(); } cout<<"点输出优先级：与原点的曼哈顿距离。\n"; point p[5]={{0,9},{12,0},{3,4},{6,5},{3,7}}; priority_queue,cmp2> que; //priority_queue que; 复杂的类型需要写出专门的比较类(上面的cmp2)。 for(int i=0;i<5;i++)que.push(p[i]); while( !que.empty() ) { point tmp=que.top(); tmp.show(); que.pop(); } return 0;}

相关的结果：

v.size:5 7 5 3 2 1 v.size:0 v2 从小到大输出： 1 2 3 5 7 自定义比较的V3输出: 1 2 3 5 7 点输出优先级：与原点的曼哈顿距离。 (12,0) (6,5) (3,7) (0,9) (3,4)

一个应用例子：

nefu 355 合成陨石

​​#include #include #include using namespace std;int main(){ int n,a; while(cin>>n){ priority_queue,greater > que; for(int i=0;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。