当前位置: 首页 > news >正文

C++ 优先级队列用法详解与模拟实现

文章目录

  • C++ 优先级队列用法与模拟实现
    • 介绍
    • 用法
      • 头文件
      • 1.创建优先级队列
        • priority_queue
      • 2. 插入元素
        • push
      • 3. 删除元素
        • pop
      • 访问顶部元素
        • top
      • 检查优先级队列的大小
        • size
      • 检查优先级队列是否为空
        • empty
    • 模拟实现

C++ 优先级队列用法与模拟实现

介绍

优先级队列(Priority Queue)是一种抽象数据类型,它类似于队列,但是每个元素都有一个优先级或权重。在优先级队列中,元素的出队顺序是按照优先级来进行的,而不是先进先出(FIFO)或后进先出(LIFO)。
在 C++ 中,优先级队列是通过 std::priority_queue 实现的,它是 C++ 标准库的一部分。std::priority_queue 是一个模板容器适配器,它提供常数时间复杂度的插入操作和 logarithmic 时间复杂度的删除操作。

用法

头文件

要使用 std::priority_queue,你需要包含 <queue> 头文件。

#include <queue>

1.创建优先级队列

在这里插入图片描述

priority_queue
  • (1)
    构造函数,可以接受两个参数,一个比较函数和一个容器。是个显式构造,不用隐式类型转换。
  • (2)
    接受两个迭代器的构造函数,它允许你从一个范围 [first, last) 中的元素初始化优先级队列
//(1)
priority_queue<int> pq1; // 创建一个整数类型的优先级队列
priority_queue<int, vector<int>, less<int>> pq2;//创建一个以vector作为底层容器类型的优先级队列,less是大堆
priority_queue<int, vector<int>, greater<int>> pq3; // 创建一个以vector作为底层容器类型的优先级队列,greater是小堆//(2)
vector<int> vec = { 4, 1, 3, 2 };
priority_queue<int> pq(vec.begin(), vec.end());//pq 会用 vec 中的元素进行初始化,并按照最大堆的顺序排列

2. 插入元素

在这里插入图片描述

push
  • 向优先级队列中插入元素。
pq.push(30);
pq.push(10);
pq.push(20);

3. 删除元素

在这里插入图片描述

pop
  • 从优先级队列中删除具有最高优先级的元素。
pq.pop(); // 删除元素 30

访问顶部元素

在这里插入图片描述

top
  • 访问优先级队列的顶部元素(具有最高优先级的元素)
int top = pq.top(); // 之前在pop中把30pop了,所以top现在是 20

检查优先级队列的大小

在这里插入图片描述

size
  • 查看优先级队列中的元素数量。
size_t size = pq.size(); // size 现在是 2

检查优先级队列是否为空

在这里插入图片描述

empty
  • 检查优先级队列是否为空。
bool isEmpty = pq.empty(); // isEmpty 现在是 false

模拟实现

下面是一个简单的优先级队列的模拟实现,使用数组和一个比较函数。

#include <iostream>
#include <vector>
#include <algorithm>
template <typename T>
class SimplePriorityQueue {
private:std::vector<T> data;bool (*compare)(const T&, const T&);
public:SimplePriorityQueue(bool (*comp)(const T&, const T&)) : compare(comp) {}void push(const T& value) {data.push_back(value);std::push_heap(data.begin(), data.end(), compare);}void pop() {std::pop_heap(data.begin(), data.end(), compare);data.pop_back();}T& top() {return data.front();}bool empty() const {return data.empty();}size_t size() const {return data.size();}
};
bool compareInt(const int& a, const int& b) {return a > b; // 大根堆
}
int main() {SimplePriorityQueue<int> pq(compareInt);pq.push(30);pq.push(10);pq.push(20);std::cout << "Top: " << pq.top() << std::endl; // 输出 30pq.pop();std::cout << "Top: " << pq.top() << std::endl; // 输出 20return 0;
}

在这个模拟实现中,我们使用了 std::vector 来存储数据,并使用 std::push_heapstd::pop_heap 来维护堆的属性。我们还需要提供一个比较函数来定义元素的优先级。

相关文章:

C++ 优先级队列用法详解与模拟实现

文章目录 C 优先级队列用法与模拟实现介绍用法头文件1.创建优先级队列priority_queue 2. 插入元素push 3. 删除元素pop 访问顶部元素top 检查优先级队列的大小size 检查优先级队列是否为空empty 模拟实现 C 优先级队列用法与模拟实现 介绍 优先级队列&#xff08;Priority Qu…...

Linux进阶之旅:深入探索Linux的高级功能

文章目录 Linux进阶之旅:深入探索Linux的高级功能1. Shell脚本编程2. 进程管理3. 网络管理4. 文本处理5. 系统监控6. 总结 Linux进阶之旅:深入探索Linux的高级功能 在上一篇博客中,我们对Linux操作系统进行了入门级的介绍,包括Linux的特点、发行版、安装方法以及基本使用。接下…...

【Java】内存可见性问题是什么?

文章目录 内存模型内存可见性解决方案volatile 内存模型 什么是JAVA 内存模型&#xff1f; Java Memory Model (JAVA 内存模型&#xff09;是描述线程之间如何通过内存(memory)来进行交互。 具体说来&#xff0c; JVM中存在一个主存区&#xff08;Main Memory或Java Heap Mem…...

Guava里一些比较常用的工具

随着java版本的更新提供了越来越多的语法和工具来简化日常开发&#xff0c;但是我们一般用的比较早的版本所以体验不到。这时就用到了guava这个包。guava提供了很多方便的工具方法&#xff0c;solar框架就依赖了guava的16.0.1版本&#xff0c;这里稍微介绍下。 一、集合工具类…...

在windows系统中【.gz.tar】和【.whl】文件分别应该怎么下载到conda的某个虚拟环境中

在 Windows 系统中&#xff0c;你可以按照以下步骤将 .gz.tar 和 .whl 文件下载到 Conda 的某个虚拟环境中&#xff1a; 激活虚拟环境&#xff1a;打开 Anaconda Prompt 或者命令行窗口&#xff0c;使用以下命令激活你想要安装文件的虚拟环境&#xff1a; conda activate <虚…...

Rust - 数据类型

Rust 是静态编译语言&#xff0c;在编译时必须知道所有变量的类型。 基于使用的值&#xff0c;编译器通常能推断出它的具体类型&#xff0c;但如果可能的类型比较多&#xff0c;例如把String转换为整数的parse方法&#xff0c;就必须添加类型的标注&#xff0c;否则编译会报错…...

基于springboot实现洗衣店订单管理系统项目【项目源码+论文说明】计算机毕业设计

基于springboot实现洗衣店订单管理系统演示 摘要 随着信息互联网信息的飞速发展&#xff0c;无纸化作业变成了一种趋势&#xff0c;针对这个问题开发一个专门适应洗衣店业务新的交流形式的网站。本文介绍了洗衣店订单管理系统的开发全过程。通过分析企业对于洗衣店订单管理系统…...

Java基础知识总结(53)

&#xff08;1&#xff09;集合框架概述 Java集合大致分为List、Set、Map和Queue Collection是一个顶级接口&#xff0c;其子接口有&#xff0c;List、Set、Queue List:有序&#xff08;存放和取出顺序是一致的&#xff09;、有索引、可重复 Set:无序、无索引、不可重复 &…...

196算法之谜在 JSP 中使用内置对象 request 获取 form 表单的文本框 text 提交的数据。

(1&#xff09;编写 inputNumber . jsp &#xff0c;该页面提供一个 form 表单&#xff0c;该 form 表单提供一个文本框 text &#xff0c;用于用户输入一个正整数&#xff0c;用户在 form 表单中输入的数字&#xff0c;单击 submit 提交键将正整数提交给 huiwenNumber . jsp 页…...

初识责任链模式--一起学习吧之数据库

一、定义 责任链模式是一种对象行为型模式&#xff0c;用于处理请求发送者和多个请求处理者之间的耦合问题。在这种模式中&#xff0c;请求的处理者通过前一对象记住其下一个对象的引用而连成一条链。当有请求发生时&#xff0c;请求会沿着这条链传递&#xff0c;直到有对象处…...

解决Xshell登录云服务器的免密码和云服务器生成子用户问题

Xshell登录云服务器的免密码问题 前言一、Xshell登录云服务器的免密码操作实践 二、centos创建用户创建用户实操删除用户更改用户密码直接删除子用户 前言 Xshell登录云服务器免密码问题的解决方案通常涉及使用SSH密钥对。用户生成一对密钥&#xff08;公钥和私钥&#xff09;…...

webRtc生产环境实用方法

最近做了几个项目发现多个项目反反复复会出现几个高频的需求&#xff0c; 都依赖于获取系统采集设备和指定设备id获取媒体流&#xff1b;为了不在反复书写总结2个公用方法&#xff1b; 检索当前系统所有可用设备 /*** 检索当前系统所有可用设备* returns {* audioInputOption…...

Java String、StringBuffer

构造方法 通过字符数组构造,结果abc 通过字节数组构造&#xff0c;结果abc //把字符串转化为字节数组 当前代码编译环境为UTF-8&#xff0c;出现异常时&#xff0c;直接抛出异常即可。mainthrows UnsupportedEncodingException 编译环境为UTF-8&#xff0c;但是运用gb2312这个…...

LangChain调用tool集的原理剖析(包懂)

一、需求背景 在聊天场景中&#xff0c;针对用户的问题我们希望把问题逐一分解&#xff0c;每一步用一个工具得到分步答案&#xff0c;然后根据这个中间答案继续思考&#xff0c;再使用下一个工具得到另一个分步答案&#xff0c;直到最终得到想要的结果。 这个场景非常匹配la…...

如何正确使用数字化仪前端信号调理?(一)

一、前言 板卡式的数字转换器和类似测量仪器&#xff0c;比如图1所示的德思特TS-M4i系列&#xff0c;都需要为各种各样的特性信号与内部模数转换器&#xff08;ADC&#xff09;的固定输入范围做匹配。 图1&#xff1a;德思特TS-M4i系列高速数字化仪&#xff0c;包括2或4通道版…...

实验5 流程图和盒图ns图

一、实验目的 通过绘制流程图和盒图&#xff0c;熟练掌握流程图和盒图的基本原理。 能对简单问题进行流程图和盒图的分析&#xff0c;独立地完成流程图和盒图设计。 二、实验项目内容&#xff08;实验题目&#xff09; 1、用Microsoft Visio绘制下列程序的程序流程图。 若…...

[Java、Android面试]_18_详解Handler机制 常见handler面试题(非常重要,非常高频!!)

本人今年参加了很多面试&#xff0c;也有幸拿到了一些大厂的offer&#xff0c;整理了众多面试资料&#xff0c;后续还会分享众多面试资料。 整理成了面试系列&#xff0c;由于时间有限&#xff0c;每天整理一点&#xff0c;后续会陆续分享出来&#xff0c;感兴趣的朋友可关注收…...

国内开通gpt会员方法

ChatGPT镜像 今天在知乎看到一个问题&#xff1a;“平民不参与内测的话没有账号还有机会使用ChatGPT吗&#xff1f;” 从去年GPT大火到现在&#xff0c;关于GPT的消息铺天盖地&#xff0c;真要有心想要去用&#xff0c;途径很多&#xff0c;别的不说&#xff0c;国内GPT的镜像…...

使用 Meltano 将数据从 Snowflake 导入到 Elasticsearch:开发者之旅

作者&#xff1a;来自 Elastic Dmitrii Burlutskii 在 Elastic 的搜索团队中&#xff0c;我们一直在探索不同的 ETL 工具以及如何利用它们将数据传输到 Elasticsearch&#xff0c;并在传输的数据上实现 AI 助力搜索。今天&#xff0c;我想与大家分享我们与 Meltano 生态系统以及…...

第24次修改了可删除可持久保存的前端html备忘录:文本编辑框不再隐藏,又增加了哔哩哔哩搜索和必应搜索

第24次修改了可删除可持久保存的前端html备忘录:文本编辑框不再隐藏&#xff0c;又增加了哔哩哔哩搜索和必应搜索. <!DOCTYPE html> <html lang"zh"><head><meta charset"UTF-8"><meta name"viewport" content"…...

抖音增长新引擎:品融电商,一站式全案代运营领跑者

抖音增长新引擎&#xff1a;品融电商&#xff0c;一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中&#xff0c;品牌如何破浪前行&#xff1f;自建团队成本高、效果难控&#xff1b;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...

转转集团旗下首家二手多品类循环仓店“超级转转”开业

6月9日&#xff0c;国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解&#xff0c;“超级…...

3-11单元格区域边界定位(End属性)学习笔记

返回一个Range 对象&#xff0c;只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意&#xff1a;它移动的位置必须是相连的有内容的单元格…...

初学 pytest 记录

安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...

区块链技术概述

区块链技术是一种去中心化、分布式账本技术&#xff0c;通过密码学、共识机制和智能合约等核心组件&#xff0c;实现数据不可篡改、透明可追溯的系统。 一、核心技术 1. 去中心化 特点&#xff1a;数据存储在网络中的多个节点&#xff08;计算机&#xff09;&#xff0c;而非…...

密码学基础——SM4算法

博客主页&#xff1a;christine-rr-CSDN博客 ​​​​专栏主页&#xff1a;密码学 &#x1f4cc; 【今日更新】&#x1f4cc; 对称密码算法——SM4 目录 一、国密SM系列算法概述 二、SM4算法 2.1算法背景 2.2算法特点 2.3 基本部件 2.3.1 S盒 2.3.2 非线性变换 ​编辑…...

基于单片机的宠物屋智能系统设计与实现(论文+源码)

本设计基于单片机的宠物屋智能系统核心是实现对宠物生活环境及状态的智能管理。系统以单片机为中枢&#xff0c;连接红外测温传感器&#xff0c;可实时精准捕捉宠物体温变化&#xff0c;以便及时发现健康异常&#xff1b;水位检测传感器时刻监测饮用水余量&#xff0c;防止宠物…...

WEB3全栈开发——面试专业技能点P4数据库

一、mysql2 原生驱动及其连接机制 概念介绍 mysql2 是 Node.js 环境中广泛使用的 MySQL 客户端库&#xff0c;基于 mysql 库改进而来&#xff0c;具有更好的性能、Promise 支持、流式查询、二进制数据处理能力等。 主要特点&#xff1a; 支持 Promise / async-await&#xf…...

leetcode73-矩阵置零

leetcode 73 思路 记录 0 元素的位置&#xff1a;遍历整个矩阵&#xff0c;找出所有值为 0 的元素&#xff0c;并将它们的坐标记录在数组zeroPosition中置零操作&#xff1a;遍历记录的所有 0 元素位置&#xff0c;将每个位置对应的行和列的所有元素置为 0 具体步骤 初始化…...

Python第七周作业

Python第七周作业 文章目录 Python第七周作业 1.使用open以只读模式打开文件data.txt&#xff0c;并逐行打印内容 2.使用pathlib模块获取当前脚本的绝对路径&#xff0c;并创建logs目录&#xff08;若不存在&#xff09; 3.递归遍历目录data&#xff0c;输出所有.csv文件的路径…...