STL --- 2、容器 (8)priority_queue

news/2024/5/20 21:21:34

目录

1、std::priority_queue的特点

2、std::priority_queue常用api

3、std::priority_queue应用场景

4、std::priority_queue实例


std::priority_queue是一个STL容器,它是一个优先队列,每个元素都有一个权值,优先级高的元素排在队列的前面。

1、std::priority_queue的特点

(1)插入元素时,自动按照优先级排序,优先级高的元素在队列的前面。

(2)删除元素时,自动删除队列中优先级最高的元素。

(3)可以使用自定义的比较函数来定义元素的优先级。

(4)内部实现是基于堆的数据结构,插入和删除元素的时间复杂度为O(logN)。

(5)支持随机访问,但不支持迭代器。

(6)可以用作最小堆或最大堆,根据比较函数的定义。

(7)不能访问队列中间的元素,只能访问队首和队尾的元素。

2、std::priority_queue常用api

1. push():将元素插入到优先队列中,自动按照优先级排序。2. top():返回优先队列中优先级最高的元素,即队首元素。3. pop():删除优先队列中优先级最高的元素,即队首元素。4. size():返回优先队列中元素的个数。5. empty():判断优先队列是否为空,如果为空返回true,否则返回false。6. swap():交换两个优先队列的元素。7. emplace():在优先队列中构造元素。8. priority_queue():构造函数,创建一个空的优先队列。9. priority_queue(Compare cmp):构造函数,创建一个空的优先队列,并指定比较函数。10. priority_queue(const priority_queue& pq):拷贝构造函数,创建一个新的优先队列,与原队列内容相同。

3、std::priority_queue应用场景

(1)任务调度:在多任务系统中,可以使用std::priority_queue来实现任务的优先级调度,将优先级高的任务先执行。

(2)事件处理:在事件驱动的系统中,可以使用std::priority_queue来存储事件,并按照事件的优先级进行处理。

(3)最短路径算法:在图论算法中,可以使用std::priority_queue来实现Dijkstra算法和Prim算法,找出最短路径或最小生成树。

(4)贪心算法:在贪心算法中,可以使用std::priority_queue来存储贪心策略中的选择集合,并按照选择的优先级进行选择。

(5)堆排序:std::priority_queue本身就是一个堆,可以使用它来实现堆排序算法。

4、std::priority_queue实例

#include <iostream>
#include <queue>int main() {std::priority_queue<int> pq;pq.push(10);pq.push(30);pq.push(20);std::cout << "Top element: " << pq.top() << std::endl;pq.pop();std::cout << "Top element after pop: " << pq.top() << std::endl;return 0;
}

输出:

Top element: 30
Top element after pop: 20

在这个例子中,我们创建了一个std::priority_queue对象pq,并使用push()函数添加三个整数值。然后,我们使用top()函数获取队列中的最高优先级元素,并使用pop()函数将其删除。最后,我们再次使用top()函数获取队列中的最高优先级元素。


https://www.xjx100.cn/news/344544.html

相关文章

OpenGL之纹理

文章目录 什么是纹理加载与创建纹理stb_image.h加载并生成纹理 纹理环绕方式纹理过滤多级渐远纹理 纹理单元 什么是纹理 我们已经了解到&#xff0c;我们可以为每个顶点添加颜色来增加图形的细节&#xff0c;从而创建出有趣的图像。但是&#xff0c;如果想让图形看起来更真实&a…

dvwa靶场通关(一)

第一关&#xff1a;Brute force low 账号是admin&#xff0c;密码随便输入 用burp suite抓包 爆破得出密码为password 登录成功 Medium 中级跟low级别基本一致&#xff0c;分析源代码我们发现medium采用了符号转义&#xff0c;一定程度上防止了sql注入&#xff0c;采用暴力破…

Android 12.0默认开启无障碍服务权限和打开默认apk无障碍服务

1.概述 在12.0的系统rom定制化开发中,在第三方app开发中,需要开启无障碍服务功能,就不需要在代码中开启无障碍服务了, 为了简便就需要在系统中开启无障碍服务,来实现开启无障碍服务功能 2. 默认开启无障碍服务权限和打开默认apk无障碍服务核心代码 frameworks/base/core…

GDB调试工具

GDB&#xff08;GNU Debugger&#xff09;是一个功能强大的命令行调试工具&#xff0c;用于调试 C、C 程序以及其他编程语言的程序。它是 GNU 项目的一部分&#xff0c;可在多个操作系统上使用&#xff0c;包括 Linux、macOS 和 Windows&#xff08;通过 MinGW 或 Cygwin&#…

Tomcat服务器、Servlet生命周期、上传下载文件、使用XHR请求数据、注解使用

文章目录 Servlet认识Tomcat服务器使用Maven创建Web项目创建Servlet探究Servlet的生命周期解读和使用HttpServletWebServlet注解详解使用POST请求完成登陆上传和下载文件下载文件上传文件 使用XHR请求数据重定向与请求转发重定向请求转发 ServletContext对象初始化参数 Servlet…

面试题基础篇

文章目录 1、二分查找2、冒泡排序3、选择排序4、插入排序5、希尔排序6、快速排序7、ArrayList8、Iterator9、LinkedList10、HashMap10.1、基本数据结构底层数据结构&#xff0c;1.7和1.8有什么不同&#xff1f; 10.2、树化与退化为何要用红黑树&#xff0c;为何一上来不树化&am…

蓝精灵协会:如何将传统 IP 融入 Web3

作者&#xff1a;Cedric Hervet&#xff0c;联合创始人&#xff0c;创意总监 我和许多项目合作过&#xff0c;并且担任了近 30 年的艺术总监和创意总监。我的方法一直是创造同质化的宇宙&#xff0c;把观众带入并使他们产生梦想。但我也曾系统地寻找过那份额外的感动&#xff1…

使用JMeter+Grafana+Influxdb搭建可视化性能测试监控平台

【背景说明】 使用jmeter进行性能测试时&#xff0c;工具自带的查看结果方式往往不够直观和明了&#xff0c;所以我们需要搭建一个可视化监控平台来完成结果监控&#xff0c;这里我们采用三种JMeterGrafanaInfluxdb的方法来完成平台搭建 【实现原理】 通过influxdb数据库存储…