转自，感谢大佬。

优先队列

引入

优先队列是一种特殊的队列，在学习堆排序的时候就有所了解，点“”查看。

那么优先队列是什么呢？

说白了，就是一种功能强大的队列。

它的功能强大在哪里呢？

四个字：自动排序。

优先队列的头文件&&声明

首先，你需要

#include
     
      using namespace std;
     

　　

这两个头文件。

其次，一个优先队列声明的基本格式是： 

priority_queue<结构类型> 队列名; 

比如：

priority_queue 
     
       i;priority_queue 
      
        d;
      
     

不过，我们最为常用的是这几种：

priority_queue 
     
       q;//node是一个结构体//结构体里重载了‘<’小于符号priority_queue 
      
       
        ,greater
        
          > q;//不需要#include
         
          头文件//注意后面两个“>”不要写在一起，“>>”是右移运算符priority_queue 
          
           
            ,less
            
              >q;
            
           
          
         
        
       
      
     

　　

我们将在下文来讲讲这几种声明方式的不同。

优先队列的基本操作

以一个名为q的优先队列为例。

q.size();//返回q里元素个数q.empty();//返回q是否为空，空则返回1，否则返回0q.push(k);//在q的末尾插入kq.pop();//删掉q的第一个元素q.top();//返回q的第一个元素q.back();//返回q的末尾元素

　　

优先队列的特性

上文已经说过了，自动排序。 

怎么个排法呢？ 

在这里介绍一下：

默认的优先队列（非结构体结构）

priority_queue 
     
       q;
     

 

这样的优先队列是怎样的？让我们写程序验证一下。

#include
     
      #include
      
       using namespace std;priority_queue 
       
         q;int main(){    q.push(10),q.push(8),q.push(12),q.push(14),q.push(6);    while(!q.empty())        printf("%d ",q.top()),q.pop();}
       
      
     

　

程序大意就是在这个优先队列里依次插入10、8、12、14、6，再输出。 

结果是什么呢？ 

14 12 10 8 6 

也就是说，它是按从大到小排序的！

默认的优先队列（结构体，重载小于）

先看看这个结构体是什么。

struct node{    int x,y;    bool operator < (const node & a) const    {        return x

这个node结构体有两个成员，x和y，它的小于规则是x小者小。 

再来看看验证程序：

#include
     
      #include
      
       using namespace std;struct node{    int x,y;    bool operator < (const node & a) const    {        return x
       
         q;int main(){    k.x=10,k.y=100;    q.push(k);    k.x=12,k.y=60;    q.push(k);    k.x=14,k.y=40;    q.push(k);    k.x=6,k.y=80;    q.push(k);    k.x=8,k.y=20;    q.push(k);    while(!q.empty())    {        node m=q.top();        q.pop();        printf("(%d,%d) ",m.x,m.y);    }}
       
      
     

　　

程序大意就是插入(10,100),(12,60),(14,40),(6,20),(8,20)这五个node。

再来看看它的输出：

(14,40) (12,60) (10,100) (8,20) (6,80)

它也是按照重载后的小于规则，从大到小排序的。

less和greater优先队列

还是以int为例，先来声明：

priority_queue 
     
      
       ,less
       
         > p;priority_queue 
        
         
          ,greater
          
            > q;
          
         
        
       
      
     

话不多说，上程序和结果：

#include
     
      #include
      
       using namespace std;priority_queue 
       
        
         ,less
         
           > p;priority_queue 
          
           
            ,greater
            
              > q;int a[5]= {10,12,14,6,8};int main(){ for(int i=0; i<5; i++) p.push(a[i]),q.push(a[i]); printf("less
             
              :") while(!p.empty()) printf("%d ",p.top()),p.pop(); pritntf("\ngreater
              
               :") while(!q.empty()) printf("%d ",q.top()),q.pop();}
              
             
            
           
          
         
        
       
      
     

　

结果： 

less<int>:14 12 10 8 6 

greater<int>:6 8 10 12 14

所以，我们可以知道，less是从大到小，greater是从小到大。

作个总结

为了方便，在平时，建议大家写：

priority_queue
     
      
       ,less
       
         >q;priority_queue
        
         
          ,greater
          
            >q;
          
         
        
       
      
     

　　

平时如果用从大到小不用后面的vector<int>,less<int>，可能到时候要改成从小到大，你反而会搞忘怎么写greater<int>，反而得不偿失。

总结

优先队列到此就作了个小结。

其实不管是队列，还是优先队列，都不仅仅只有我讲的这些，还有更多可以探索。

学，无止境。