# :-: **优先队列(priority\_queue)** ## **什么是优先队列** * 说白了，就是一种功能强大的队列， 它的功能强大在哪里呢？ 四个字：自动排序。 * 既然优先队列也是一种队列，那么自然使用同样的头文件。 其次，一个优先队列声明的基本格式是： priority_queue<结构类型> 队列名; 比如： ``` priority_queue <int> i; priority_queue <double> d; ``` 不过，我们最为常用的是这几种： ``` priority_queue <node> q; //node是一个结构体 //结构体里重载了‘<’小于符号 priority_queue <int,vector<int>,greater<int> > q; //不需要#include<vector>头文件 //注意后面两个“>”不要写在一起，“>>”是右移运算符 priority_queue <int,vector<int>,less<int> >q; ``` 我们将在下文来讲讲这几种声明方式的不同。 ## **优先队列的基本操作** 与队列的基本操作如出一辙。 如果想要了解请点击这里，看关于队列的介绍。 以一个名为q的优先队列为例。 ``` q.size();//返回q里元素个数 q.empty();//返回q是否为空，空则返回1，否则返回0 q.push(k);//在q的末尾插入k q.pop();//删掉q的第一个元素 q.top();//返回q的第一个元素 ``` 优先队列的特性 上文已经说过了，自动排序。 怎么个排法呢？ 在这里介绍一下： 默认的优先队列（非结构体结构） `priority_queue <int> q;` 这样的优先队列是怎样的？让我们写程序验证一下。 ``` #include<cstdio> #include<queue> using namespace std; priority_queue <int> 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<a.x; } }; ``` 这个node结构体有两个成员，x和y，它的小于规则是x大者优先。 再来看看验证程序： ``` #include<cstdio> #include<queue> using namespace std; struct node { int x,y; bool operator < (const node & a) const { return x<a.x; } }k; priority_queue <node> 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 <int,vector<int>,less<int> > p; priority_queue <int,vector<int>,greater<int> > q; ``` **再次强调：“>”不要两个拼在一起。** 话不多说，上程序和结果： ``` #include<cstdio> #include<queue> using namespace std; priority_queue <int,vector<int>,less<int> > p; priority_queue <int,vector<int>,greater<int> > 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<int>:")； while(!p.empty()) printf("%d ",p.top()),p.pop(); printf("\ngreater<int>:")； 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是从小到大**。