admin管理员组文章数量:1624353
priority_queue 优先级队列,鄙人以为这是一种很重要的迭代器,重要到是图论位必备技能。
掌握好priority_queue是为了后期学Dijkstra和SPFA等图论算法的基础。
priority_queue 介绍
priority_queue 优先队列的核心操作是支持在常量时间内获得最优先的元素。priority_queue 的难点就在于如何构造优先队列,更具体的说是如何使用自己定义的结构作为优先队列中的元素。
priority_queue 对于基本类型的使用方法相对简单。他的模板声明带有三个参数,priority_queue
Type 为数据类型
Container 为保存数据的容器
Functional 为元素比较方式。
Container 必须是用数组实现的容器,比如 vector, deque 但不能用 list。STL里面容器默认用的是 vector. 比较方式默认用 operator< , 所以如果你把后面俩个参数缺省的话,优先队列就是大顶堆,队头元素最大。
priority_queue 功能函数
创建 priority_queue
priority_queue ()
例如:priority_queue pq;
prioriy_queue (const priority_queue &)
例如:priority_queue pq2(pq);
元素入队
void push(const value_type &x)
元素出队
void pop()
取队首元素
const value_type& top() const
队列非空判断
bool empty()
队列中元素个数
size_type size() // size_type为一个无符号整数
总的来说以下各种重载就是,重载一下小于号的操作而已!!
就像:priority_queue,cmp> q;
构建优先队列
例一:构建一个 int 型大顶堆,队头元素最大 (如果需要一个小顶堆,将仿函数 less 修改为 greater)
#include
例二:自定义数据类型的优先队列
对于自定义类型,则必须自己重载 operator< 或者自己写仿函数:
(1) 自定义类型重载 operator<
重载 operator< 后,声明对象时就可以只带一个模板参数。此时不能像基本类型这样声明 priority_queue, greater >。例如建立一个分别按照 x, y 值的升序优先队列
结构体外的重载
#include
结构体内的重载
#include
(2) 自己写仿函数
实现带仿函数的声明,如:priority_queue, greater >
#include
好了谢谢大家阅读鸭
温馨提示
如果你喜欢本文,请分享到朋友圈,想要获得更多信息,请关注ACM算法日常。
点赞的时候,请宠溺一点本文标签: 队列优先级stl是小顶堆吗priorityqueue
版权声明:本文标题:优先队列默认是小顶堆吗_STL 之 priority_queue 优先级队列 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/dianzi/1728897718a1178626.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论