C++的优先队列priority_queue
什么是优先队列
优先队列(priority queue) 普通的队列是一种先进先出的数据结构,元素在队列尾追加,而从队列头删除。在优先队列中,元素被赋予优先级。当访问元素时,具有最高优先级的元素最先删除。优先队列具有优先级最高先出的性质。通常采用堆数据结构来实现。
优先队列的原理
std::priority_queue
在优先队列中,优先级高的元素先出队列,并非按照先进先出的要求,类似一个堆heap
。其模板声明带有三个参数,priority_queue<Type, Container, Functional>
, 其中Type
为数据类型,Container
为保存数据的容器,Functional
为元素比较方式。Container
必须是用数组实现的容器,比如 vector
, deque
. STL
里面默认用的是vector
. 比较方式默认用operator<
, 所以如果把后面两个参数缺省的话,优先队列就是大顶堆,队头元素最大。
优先队列常常用堆heap
来实现。堆是一个完全二叉树,其每个节点的值总是大于等于子节点的值。实际实现堆时,我们通常用一个数组而不是用指针建立一个树。这是因为堆是完全二叉树,所以用数组表示时,位置i
的节点的父节点位置一定为 i/2
,而它的两个子节点的位置
又一定分别为 2i 1
和 2i 2
。
以下是堆的实现方法,其中最核心的两个操作是 上浮 swim 和下沉sink:如果一个节点比父节点大,那么需要交换这个两个节点;交换后还可能比它新的父节点大,因此需要不断地进行比较和交换操作,我们称之为上浮;类似地,如果一个节点比父节小,也需要不断地向下进行比较和交换操作,我们称之为下沉。如果一个节点有两个子节点,我们总是交换最大的子节点。
如何定义
priority_queue<>
尖括号里写数据类型,容器名称和排列规则
- 数据类型可以是
int
char
double
string
等等 - 容器名称一般使用
vector动态数组
- 排列规则一般是大根堆或者小根堆,表示最大或最小的优先级别最高
但有一种特殊情况,数据类型为结构体时,第二个和第三个都可省略,容器名称默认是vector
(关于可变长数组可看本人创作的C 中的可变长数组(vector),每个成员都是结构体,排列规则是根据某一个元素的大小进行排序,就和sort
(关于快速排列可看本人创作的C 中的快速排列(sort))里的cmp
是一个道理,优先队列排列规则默认为operator<
但是注意,在operator<
里的比较规则和cmp
恰恰相反!比如在cmp
里,a.x>b.x
表示按x
的降序排列,但在operator<
里则是升序排;同样的greater
在cmp
里表示表示升序,然而在operator<
里则代表降序。
举个例子:
#include<bits/stdc .h>
using namespace std;
struct node
{
int id,shu,yu;
};
bool operator<(node a,node b)
{
return a.shu>b.shu;
}
int main()
{
priority_queue<node>q;
int i,n,a,b,c;
cin>>n;
for(i=1;i<=n;i )
{
cin>>a>>b>>c;
q.push({a,b,c});
}
while(!q.empty())
{
cout<<q.top().id<<" "<<q.top().shu<<" "<<q.top().yu<<endl;
q.pop();
}
return 0;
}
这里注意一点:如果第三项的排列规则没有省略,后面的尖括号与优先队列的尖括号之间一定要有空格,否则电脑会把它识别为右移运算符,会报错:
priority_queue<int,vector<int>,less<int> >q;
常用的函数:
empty();
用来判断这个队列是否为空,不为空返回假,否则返回真
pop();
将优先级最高的元素删除
push();
队尾插入一个元素,如果要插多个,要打{}
size();
返回元素的个数
top()
返回队首元素
今天就讲这么多关于优先队列的内容,如果有不懂的问题,欢迎留在评论区哦
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgfbbkj
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01