首页 > 代码库 > priority_quenue

priority_quenue

转自:http://blog.csdn.net/xiaoquantouer/article/details/52015928

http://www.cnblogs.com/cielosun/p/5654595.html

1、头文件

#include<queue>


2、定义

[cpp] view plain copy 技术分享技术分享
  1. priority_queue<int> p;  


3、优先输出大数据  虽然用的是less结构,然而,队列的出队顺序却是greater的先出!

priority_queue<Type, Container, Functional>

Type为数据类型, Container为保存数据的容器,Functional为元素比较方式。

如果不写后两个参数,那么容器默认用的是vector,比较方式默认用operator<,也就是优先队列是大顶堆,队头元素最大。


例如:

[cpp] view plain copy 技术分享技术分享
  1. #include<iostream>  
  2. #include<queue>  
  3. using namespace std;  
  4.   
  5. int main(){  
  6.     priority_queue<int> p;  
  7.     p.push(1);  
  8.     p.push(2);  
  9.     p.push(8);  
  10.     p.push(5);  
  11.     p.push(43);  
  12.     for(int i=0;i<5;i++){  
  13.         cout<<p.top()<<endl;  
  14.         p.pop();  
  15.     }  
  16.     return 0;  
  17. }  



输出:


技术分享



4、优先输出小数据

方法一:

[cpp] view plain copy 技术分享技术分享
  1. priority_queue<int, vector<int>, greater<int> > p;  



例如:

[cpp] view plain copy 技术分享技术分享
  1. #include<iostream>  
  2. #include<queue>  
  3. using namespace std;  
  4.   
  5. int main(){  
  6.     priority_queue<int, vector<int>, greater<int> >p;  
  7.     p.push(1);  
  8.     p.push(2);  
  9.     p.push(8);  
  10.     p.push(5);  
  11.     p.push(43);  
  12.     for(int i=0;i<5;i++){  
  13.         cout<<p.top()<<endl;  
  14.         p.pop();  
  15.     }  
  16.     return 0;  
  17. }  



输出:

技术分享



方法二:自定义优先级,重载默认的 < 符号


例子:

[cpp] view plain copy 技术分享技术分享
  1. #include<iostream>  
  2. #include<queue>  
  3. #include<cstdlib>  
  4. using namespace std;  
  5. struct Node{  
  6.     int x,y;  
  7.     Node(int a=0, int b=0):  
  8.         x(a), y(b) {}  
  9. };  
  10.   
  11. struct cmp{  
  12.     bool operator()(Node a, Node b){  
  13.         if(a.x == b.x)  return a.y>b.y;  
  14.         return a.x>b.x;  
  15.     }  
  16. };  
  17.   
  18. int main(){  
  19.     priority_queue<Node, vector<Node>, cmp>p;  
  20.       
  21.     for(int i=0; i<10; ++i)  
  22.         p.push(Node(rand(), rand()));  
  23.           
  24.     while(!p.empty()){  
  25.         cout<<p.top().x<<‘ ‘<<p.top().y<<endl;  
  26.         p.pop();  
  27.     }//while  
  28.     //getchar();  
  29.     return 0;  
  30. }  



输出:

技术分享

priority_quenue