admin管理员组文章数量:1623797
一、基本介绍:
在
C
+
+
C++
C++中,存在一个十分有效的
S
T
L
STL
STL中的数据结构:优先队列。它定义在#include <queue>
这个头文件中。优先队列基本相当于一个封装好的堆,可以根据你的需求对堆进行一系列的操作。
二、基本用法:
1.头文件:
#include <queue>
2.定义:
priority_queue<Type,Container,Functional> q;
Type
就是数据类型,Container
就是容器类型(Container
必须是用数组实现的容器,比如vector
,deque
等等,但不能用list
。 S T L STL STL里面默认用的是vector
),Functional
就是比较的方式,当需要用自定义的数据类型时需要传入这三个参数。比如:
priority_queue<int,vector<int>,greater<int> >//小根堆
priority_queue<int,vector<int>,less<int> >//大根堆
- 使用基本数据类型时,只需要传入数据类型,并在没有
Functional
参数的情况下,默认是大顶堆。比如:priority_queue<int> q
3.用法:
q.top() 返回堆顶元素
q.empty() 判断堆是否为空,返回true表示空,返回false表示非空
q.size() 返回一个整型变量表示堆中元素的个数
q.push() 插入元素到堆中 (并维护堆)
q.pop() 弹出堆顶元素
4.程序实例
- 程序如下:
#include <iostream>
#include <queue>
using namespace std;
int main()
{
priority_queue<int> a;
for(int i=0;i<5;i++)
{
a.push(i);
c.push(i);
}
while(!a.empty())
{
cout<<a.top()<<" ";
a.pop();
}
cout<<endl;
return 0;
}
- 结果如下:
4 3 2 1 0
三、高级应用(对自定义类型的操作):
1.由于是自定义类型,所以只能自己定义变量之间的大小关系,于是这里就涉及到了
C
+
+
C++
C++中重载运算符的操作
2.具体的操作如下(以大根堆为例):
struct node
{
ll val;
ll depth;
bool operator<(const node a)const
{
if(val!=a.val)
return val>a.val;
return depth>a.depth;
}
};
priority_queue<node,vector<node>,less<node> > s;
3.重载运算符
<
<
<实际上就是自定义当出现
b
<
a
b<a
b<a且
a
a
a,
b
b
b都为node
类型的时候返回值的情况。const node a
在
<
<
<后面,所以代表的是b<a中的第二个变量。
4.两个const
必须要加上去,这是重载运算符的格式,不能省略,否则会编译失败
四、题目推荐:
既然学习了优先队列,自然要学习巩固啦,所以在这里推荐一些题目,希望大家能够有所收获:
POJ1456 Supermarket,POJ2442 Sequence,洛谷P3620 数据备份,洛谷P1091 合并果子,洛谷P2168 荷马史诗
本文标签: 队列stlpriorityqueue
版权声明:本文标题:STL优先队列(priority_queue)——用法解析 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/dongtai/1728897049a1178544.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论