c++优先队列(priority_queue)用法详解
发布日期:2021-09-12 06:44:51 浏览次数:1 分类:技术文章

本文共 2546 字,大约阅读时间需要 8 分钟。

既然是队列那么先要包含头文件#include <queue>, 他和queue不同的就在于我们可以自定义其中数据的优先级, 让优先级高的排在队列前面,优先出队

优先队列具有队列的所有特性,包括基本操作,只是在这基础上添加了内部的一个排序,它本质是一个堆实现的

和队列基本操作相同:

  • top 访问队头元素
  • empty 队列是否为空
  • size 返回队列内元素个数
  • push 插入元素到队尾 (并排序)
  • emplace 原地构造一个元素并插入队列
  • pop 弹出队头元素
  • swap 交换内容

定义:priority_queue<Type, Container, Functional>

Type 就是数据类型,Container 就是容器类型(Container必须是用数组实现的容器,比如vector,deque等等,但不能用 list。STL里面默认用的是vector),Functional 就是比较的方式,当需要用自定义的数据类型时才需要传入这三个参数,使用基本数据类型时,只需要传入数据类型,默认是大顶堆
一般是:

//升序队列priority_queue 
,greater
> q;//降序队列priority_queue
,less
>q;//greater和less是std实现的两个仿函数(就是使一个类的使用看上去像一个函数。其实现就是类中实现一个operator(),这个类就有了类似函数的行为,就是一个仿函数类了)

  1. 基本类型例子:
#include
#include
using namespace std;int main() { //对于基础类型 默认是大顶堆 priority_queue
a; //等同于 priority_queue
, less
> a; priority_queue
, greater
> c; //这样就是小顶堆 priority_queue
b; for (int i = 0; i < 5; i++) { a.push(i); c.push(i); } while (!a.empty()) { cout << a.top() << ' '; a.pop(); } cout << endl; while (!c.empty()) { cout << c.top() << ' '; c.pop(); } cout << endl; b.push("abc"); b.push("abcd"); b.push("cbd"); while (!b.empty()) { cout << b.top() << ' '; b.pop(); } cout << endl; return 0;}

输出

4 3 2 1 00 1 2 3 4cbd abcd abc

2.pari的比较,先比较第一个元素,第一个相等比较第二个

#include 
#include
#include
using namespace std;int main() { priority_queue
> a; pair
b(1, 2); pair
c(1, 3); pair
d(2, 5); a.push(d); a.push(c); a.push(b); while (!a.empty()) { cout << a.top().first << ' ' << a.top().second << '\n'; a.pop(); }}

输出

2 51 31 2

3.对于自定义类型

#include 
#include
using namespace std;//方法1struct tmp1 //运算符重载<{ int x; tmp1(int a) {x = a;} bool operator<(const tmp1& a) const { return x < a.x; //大顶堆 }};//方法2struct tmp2 //重写仿函数{ bool operator() (tmp1 a, tmp1 b) { return a.x < b.x; //大顶堆 }};int main() { tmp1 a(1); tmp1 b(2); tmp1 c(3); priority_queue
d; d.push(b); d.push(c); d.push(a); while (!d.empty()) { cout << d.top().x << '\n'; d.pop(); } cout << endl; priority_queue
, tmp2> f; f.push(c); f.push(b); f.push(a); while (!f.empty()) { cout << f.top().x << '\n'; f.pop(); }}

输出

321321

转载地址:https://blog.csdn.net/weixin_36888577/article/details/79937886 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:进程调度与死锁
下一篇:区分operator++()是前缀还是后缀自增

发表评论

最新留言

路过,博主的博客真漂亮。。
[***.116.15.85]2024年03月28日 16时53分50秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

ab753变频器参数怎么拷贝到面板_变频器不知道如何上手,厂家教你如何三点搞定设置变频器参数... 2019-04-21
keepalived mysql双主架构图_华为CRM资深架构师:MySQL数据库架构和同步复制流程,看完就懂... 2019-04-21
gradle 本地maven仓库_Gradle的使用教程 2019-04-21
python制作表格处理软件_震惊!当Python遇到Excel后,将开启你的认知虫洞 2019-04-21
手写一个promise用法_手写系列之实现一个Promise 2019-04-21
数字拆分问题算法回溯_学会了回溯算法,我终于会做数独了 2019-04-21
广州刷脸支付骗局_刷脸支付是骗局?那可能你还不了解刷脸支付 2019-04-21
卸载源码安装的mysql_源码安装与卸载mysql 2019-04-21
mysql查询当天记录_sql查询当天记录 2019-04-21
java 远程调试 端口_JAVA远程调试 2019-04-21
java 获取 html 图片路径_JAVA-替换html中图片的路径-从html代码中提取图片路径并下载(完整版)... 2019-04-21
java redis 面试题_Java面试题(Redis篇) 2019-04-21
java 正则表达式分类功能_JAVA正则表达式4种常用功能 2019-04-21
java3d立方体_3d立方体贴图 2019-04-21
java ajax教程_(转)JAVA AJAX教程第三章—AJAX详细讲解 2019-04-21
java operators_A guide to Java Operators 2019-04-21
java socket调试_JAVA实现SOCKET多客户端通信的案例 2019-04-21
java 使用或覆盖了已过时的api_JAVA使用或覆盖了已过时的 API 2019-04-21
java 图片旋转保存_Java 对图片90度旋转 2019-04-21
用java实现文学研究助手_数据结构文学研究助手 C语言代码实现(带源码+解析)... 2019-04-21