优先队列——Priority_Queue详解

一、入门介绍

&＃xff11;、 优先队列是一种特殊的队列&＃xff0c;这种队列会自动的把队列里的数排序(默认从大到小&＃xff0c;使用“<”判断),而且还可以把数按照特定的方法排列&＃xff01;(包括结构体和重载"<")
&＃xff12;、 优先队列的头文件&＃xff0c;需要包括&＃xff1a;

#include
using namespace std;


声明&＃xff1a; 一个优先队列声明的基本格式是&＃xff1a;

priority_queue<结构类型> 队列名; 比如&＃xff1a;
priority_queue i;
priority_queue d;

不过&＃xff0c;我们最为常用的是这几种&＃xff1a;

priority_queue q;//node是一个结构体//结构体里重载了‘<’小于符号
priority_queue ,greater > q;　// 从小到大排序&＃xff08;数组&＃xff09;priority_queue ,less >q;　　　// 从大到小排序//不需要#include头文件//注意后面两个“>”不要写在一起&＃xff0c;“>>”是右移运算符

二、优先队列的基本操作&＃xff1a;

&＃xff11;、以一个名为q的优先队列为例&＃xff1a;

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

&＃xff12;、优先队列的特性
自动排序。
怎么个排法呢&＃xff1f; 在这里介绍一下&＃xff1a;
(1)、默认的优先队列&＃xff08;非结构体结构&＃xff09;

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&＃xff0c;再输出。
结果是什么呢&＃xff1f;
14 12 10 8 6
也就是说&＃xff0c;它是按从大到小排序的&＃xff01;
(2)、默认的优先队列&＃xff08;结构体&＃xff0c;重载小于&＃xff09;
        先看看这个结构体是什么。

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

这个node结构体有两个成员&＃xff0c;x和y&＃xff0c;它的小于规则是x小者小。
再来看看验证程序&＃xff1a;

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


(3)、less和greater优先队列&＃xff08;多使用这一个&＃xff09;
还是以int为例&＃xff0c;先来声明&＃xff1a;

priority_queue ,less > p;　　 　// 数组从大到小排序priority_queue ,greater > q;　　// 从小到大排序

CODE:

#include
#include
using namespace std;priority_queue ,less > p;
priority_queue ,greater > q;int a[5]&＃61;{10,12,14,6,8};int main()
{for(int i&＃61;0;i<5;i&＃43;&＃43;)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();
}

结果&＃xff1a;

less:14 12 10 8 6
greater:6 8 10 12 14

所以&＃xff0c;我们可以知道&＃xff0c;less是从大到小&＃xff0c;greater是从小到大。