作者:会展小控 | 来源:互联网 | 2023-10-09 21:31
一、入门介绍
&#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是从小到大。