priority_queue的用法-白红宇

priority_queue的用法

阅读量：5086 次

发布时间：2019-06-13

本文共 4087 字，大约阅读时间需要 13 分钟。

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 
     
       2 #include 
      
        3 using namespace std; 4 int main(){ 5     priority_queue
       
         q; 6     for( int i= 0; i< 10; ++i ) q.push(i); 7     while( !q.empty() ){ 8         cout<
        
         <

　　以下代代码返回pair的比较结果，先按照pair的first元素降序，first元素相等时，再按照second元素降序：

1 #include
     
       2 #include
      
        3 #include
       
         4 using namespace std; 5 int main(){ 6     priority_queue
        
         
           > coll; 7     pair
          
            a(3,4); 8 pair
           
             b(3,5); 9 pair
            
              c(4,3);10 coll.push(c);11 coll.push(b);12 coll.push(a);13 while(!coll.empty())14 {15 cout<
             
              <<"\t"<
              
               <

2.2 如果要用到小顶堆，则一般要把模板的3个参数都带进去。STL里面定义了一个仿函数greater<>，基本类型可以用这个仿函数声明小顶堆。

　　以下代码返回一个升序输出：

1 #include 
     
       2 #include 
      
         3 using namespace std; 4 int main(){ 5     priority_queue

, greater

> 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元素相等时，再按照second元素升序：

1 #include
     
       2 #include
      
        3 #include
       
         4 using namespace std; 5 int main(){ 6     priority_queue
        
         
          ,vector
          
           
             >,greater
            
             
               > > coll; 7 pair
              
                a(3,4); 8 pair
               
                 b(3,5); 9 pair
                
                  c(4,3);10 coll.push(c);11 coll.push(b);12 coll.push(a);13 while(!coll.empty())14 {15 cout<
                 
                  <<"\t"<
                  
                   <

2.3 对于自定义类型，则必须重载operator<或者重写仿函数。

2.3.1 重载operator<的例子：返回true时，说明左边形参的优先级低于右边形参

1 #include 
     
       2 #include 
      
         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的优先级低于b10     //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
       
         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 
     
       2 #include 
      
        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的优先级大于b10     //x大的排在队前部；x相同时，y大的排在队前部11     if( a.x== b.x ) return a.y> b.y;12     return a.x> b.x; 13 }14 int main(){15     priority_queue
       
        
         ,greater
         
           > 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 
     
       2 #include 
      
        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
       
        , 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 }

参考：

转载于:https://www.cnblogs.com/Deribs4/p/5657746.html

你可能感兴趣的文章