STL库--priority_queue
目录
priority_queue定义
prority_queue容器内元素的访问
priority_queue()常用函数实例解析
priority_queue内元素优先级的设置
priority_queue的常见用途
priority_queue又称为优先队列,其底层是用堆来进行实现的。在优先队列中,队首元素一定是当前队列中优先级最高的那一个。例如在队列有如下元素,且定义好了优先级:
桃子(优先级3)
梨子(优先级4)
苹果(优先级1)
那么出队的顺序为梨子(4)、桃子(3)、苹果(1)
当然,可以在任何时候往优先队列里面加入元素,而优先队列底层的数据结构堆会随时调整结构,使得每次的队首元素都是优先级最大的。关于这里的优先级则是规定出来的。
priority_queue定义
其定义的写法和其他STL容器相同,typename可以是任意基本数据类型或容器
prioroty_queue<typename> name;
prority_queue容器内元素的访问
和队列不一样的是,优先队列没有front()函数与back()函数,而只能通过top()函数来访问队首元素,也就是优先级最高的元素。
#include<stdio.h>
#include<queue>
using namespace std;
int main(){priority_queue<int> q;q.push(3);q.push(4);q.push(1);printf("%d\n",q.top());return 0;
}
输出结果
4
priority_queue()常用函数实例解析
(1)push()
push(x)将令x入队,时间复杂度为,其中N为当前优先队列中的元素个数
(2)top()
top()可以获得队首元素,时间复杂度为
(3)pop()
pop()令队首元素出队,时间复杂度为,其中N为当前优先队列中的元素个数。
#include<stdio.h>
#include<queue>
using namespace std;
int main(){priority_queue<int> q;q.push(3);q.push(4);q.push(1);printf("%d\n",q.top());q.pop();printf("%d\n",q.top());return 0;
}
输出结果
4
3
(4)empty()
empty()检测优先队列是否为空,返回true则空,返回false则非空,时间复杂度为
#include<stdio.h>
#include<queue>
using namespace std;
int main(){priority_queue<int> q;if(q.empty()==true){printf("Empty\n");}else{printf("Not Empty\n");}q.push(1);if(q.empty()==true){printf("Empty\n");}else{printf("Not Empty\n");}return 0;
}
(5)size()
size()返回优先队列内元素的个数,时间复杂度为
#include<stdio.h>
#include<queue>
using namespace std;
int main(){priority_queue<int> q;q.push(3);q.push(4);q.push(1);printf("%d\n",q.size());return 0;
}
priority_queue内元素优先级的设置
如何定义优先队列内元素的优先级是运用好优先队列的关键,下面分别介绍基本数据类型与结构体类型的优先级设置方法。
(1)基本数据类型的优先级设置
此处指的基本数据类型就是int型,double型,char型等可以直接使用的数据类型,优先队列对它们的优先级设置一般是数字大的优先级越高,因此队首元素就是优先队列内的元素最大的那个(如果char型,则是字典序最大的)。对基本数据类型来说,下面两种优先队列的定义是等价的(以int型为例)
prioroty_queue<int> q;
priority_queue<int,vector<int>,less<int> > q;
可以发现,第二种定义方式的尖括号多出了两个参数:一个是vector<int>,另一个是less<int>。其中vector<int>填写的是来承载底层数据结构堆的容器,如果第一个参数是double型或char型,则此处只需要填写vector<double>或vector<char>;而第三个参数less<int>则是对第一个参数的比较类,less<int>表示数字大的优先级越大,而greater<int>表示数字小的优先级越大。
因此,如果想让优先队列总是把最小的元素放在队首,只需进行如下定义:
priority_queue<int,vector<int>,greater<int> > q;
#include<stdio.h>
#include<queue>
using namespace std;
int main(){priority_queue<int,vector<int>,greater<int> > q;q.push(3);q.push(4);q.push(1);printf("%d\n",q.top());return 0;
}
输出结果
1
事实上,即便是基本数据类型,也可以使用下面的结构体的优先级设置方法,只不过第三个参数的写法不太一样。
(2)结构体的优先级设置
可以举一个水果的例子,对水果的价格和名称建立一个结构体
struct fruit{string name;int price;
};
现在希望按水果的价格高的为优先级高,就需要重载小于号"<"。重载是指对已有的运算符进行重新定义,也就是说,可以改变小于号的功能,写法如下:
struct fruit{string name;int price;friend bool operator < (fruit f1,fruit f2){return f1.price < f2.price;}
};
可以看到,fruit结构体增加了一个函数,其中”friend"为友元,后面的”bool operator < (fruit f1,fruit f2)"对fruit类型的操作符“<"进行了重载(重载大于号会编译错误,因为从数学上来说只需要重载小于号,即f1>f2等价于判断f2<f1,而f1==f2等价于判断!(f1<f2)&&!(f2<f1),函数内部为"return f1.price<f2.price",因此重载后小于号还是小于号的作用。此时就可以直接定义fruit类型的优先队列,其内部就是以价格高的水果为优先级高。
priority_queue<fruit> q;
同理,如果想要以价格低的水果为优先级高,那么只需要把return中的小于号改为大于号即可。
struct fruit{string name;int price;friend bool operator < (fruit f1,fruit f2){return f1.price > f2.price;}
};
完整代码如下:
#include<iostream>
#include<string>
#include<queue>
using namespace std;
struct fruit{string name;int price;friend bool operator < (fruit f1,fruit f2){return f1.price > f2.price;}
}f1,f2,f3;
int main(){priority_queue<fruit> q;f1.name="桃子";f1.price=3;f2.name="梨子";f2.price=4;f3.name="苹果";f3.price=1;q.push(f1);q.push(f2);q.push(f3);cout<<q.top().name<<" "<<q.top().price<<endl;return 0;
}
输出结果
苹果 1
此处对小于号的重载与排序函数sort中的cmp函数有些相似,它们的参数都是两个变量,函数内部都是return了true或者false。事实上,这两者的作用确实是类似的,只不过效果看上去似乎是相反的。在排序中,如果return f1.price>f2.price,那么则是按照价格从高到低排序,但是在优先队列中却是把价格低的放在队首。原因在于,优先队列本身静默的规则就是优先级高的放在队首,因此把小于号重载为大于号的功能时只是把这个规则反向了一下。只需要记住,优先队列的这个函数与sort中的cmp函数的效果是相反的。
或者也可以把结构体定义在外面,只需要把friend去掉,把小于号改成一对小括号,然后把重载的函数写在结构体外面,同时将其用struct包装起来。
struct cmp{bool operator () (fruit f1,fruit f2){return f1.price > f2.price;}
};
在这种情况下需要用之前讲解的第二种定义方式来定义优先队列
priority_queue<fruit,vector<fruit>,cmp> q;
完整代码如下:
#include<iostream>
#include<string>
#include<queue>
using namespace std;
struct fruit{string name;int price;
}f1,f2,f3;
struct cmp{bool operator () (fruit f1,fruit f2){return f1.price > f2.price;}
};
int main(){priority_queue<fruit,vector<fruit>,cmp> q;f1.name="桃子";f1.price=3;f2.name="梨子";f2.price=4;f3.name="苹果";f3.price=1;q.push(f1);q.push(f2);q.push(f3);cout<<q.top().name<<" "<<q.top().price<<endl;return 0;
}
当然即便是基本数据类型或者其他STL容器,也可以通过同样的方式来定义优先级。
最后指出,如果结构体内的数据较为庞大(例如出现了字符串或者数组),建议使用引用来提高效率,此时比较类的参数需要加上"const"和"&"
friend bool operator < (const fruit &f1,const fruit &f2){return f1.price > f2.price;
}
bool operator() (const fruit &f1,const fruit &f2){return f1.price > f2.price;
}
priority_queue的常见用途
priority_queue可以解决一些贪心问题,也可以对Dijkstra算法进行优化。
但是注意在使用tiop()函数前,必须用empty()判断优先队列是否为空。
相关文章:
STL库--priority_queue
目录 priority_queue定义 prority_queue容器内元素的访问 priority_queue()常用函数实例解析 priority_queue内元素优先级的设置 priority_queue的常见用途 priority_queue又称为优先队列,其底层是用堆来进行实现的。在优先队列中,队首元素一定是当…...
网络编程 —— Http使用httpClient实现页面爬虫
先去找类型的a标签 取出图片所在网址 取出https://desk.3gbizhi.com/deskMV/438.html 搭建Form界面 Http类 public static HttpClient Client { get; } static Http() {HttpClientHandler handler new HttpClientHandler();//处理消息对象//ServerCertificateCustomValidat…...
【本地运行chatgpt-web】启动前端项目和service服务端项目,也是使用nodejs进行开发的。两个都运行成功才可以使用!
1,启动web界面 https://github.com/Chanzhaoyu/chatgpt-web#node https://nodejs.org/en/download/package-manager # 使用nvm 安装最新的 20 版本。 curl -o- https://raw.githubusercontent.com/nvm-sh/nvm/v0.39.7/install.sh | bash source /root/.bashrc n…...
TOGAF企业架构章节(核心)知识点(一)
TOGAF标准9.2一共有 6 部分: 第一部分(简介):企业架构的关键概念,特别是 TOGAF 方法进行了概要介绍第二部分(架构开发方法): TOGAF 框架的核心部分。描述了 TOGAF 架构开发方法&…...
手摸手教你uniapp原生插件开发
行有余力,心无恐惧 这篇技术文章写了得有两三个礼拜,虽然最近各种事情,工作上的生活上的,但是感觉还是有很多时间被浪费.还记得几年前曾经有一段时间7点多起床运动,然后工作学习,看书提升认知.现在我都要佩服那会儿的自己.如果想回到那种状态,我觉得需要有三个重要的条件. 其…...
C++进程间通信 消息队列
C进程间通信 消息队列 消息队列概述消息队列代码示例1. 创建和发送消息的程序(sender.cpp)2. 接收消息的程序(receiver.cpp) 代码解释运行步骤运行结果 消息队列概述 消息队列是一种进程间通信机制,允许一个或多个进程…...
mysql中InnoDB的统计数据
大家好。我们知道,mysql中存在许多的统计数据,比如通过SHOW TABLE STATUS 可以看到关于表的统计数据,通过SHOW INDEX可以看到关于索引的统计数据,那么这些统计数据是怎么来的呢?它们是以什么方式收集的呢?今…...
P459 包装类Wrapper
包装类的分类 1)针对八种基本数据类型相应的引用类型——包装类。 2)有了类的特点,就可以调用类中的方法。 Boolean包装类 Character包装类 其余六种Number类型的包装类 包装类和基本数据类型的相互转换 public class Integer01 {publi…...
Kong网关的负载均衡
安装java环境 查询 java安装包 196 yum list java* 安装java8197 yum install -y java-1.8.0-openjdk.x86_64 检验java8是否安装成功。198 java -version2个tomcat准备 另外一个tomcat区别在于:配置文件。conf/server.xml 启动tomcat [rootlocalhost bin]# ./…...
这是一个逗号
还不太能是句号,随想录这两个月算是给我一个学算法的开头,感慨还是挺多的,但是语文功底很差,就接着写流水账吧。 高考前想报计算机,但是那年是先报志愿后考试,家里人劝我选择更稳一点的985,又说…...
oracle tree
select * from "Test"; INSERT INTO "Test" ("id", "name", "pid") VALUES (01, 中国, 00); INSERT INTO "Test" ("id", "name", "pid") VALUES (01.01, 福建, 01); INSERT INTO…...
react-beautiful-dnd 横纵排序demo
简单导入就可以看到效果 1. 安装依赖 npm i react-beautiful-dnd 2. 纵向排序 import React, { useState } from react; import { DragDropContext, Droppable, Draggable } from react-beautiful-dnd;// 纵向排序 const reorder (list, startIndex, endIndex) > {con…...
web练习
[CISCN 2022 初赛]ezpop ThinkPHP V6.0.12LTS 反序列化漏洞 漏洞分析 ThinkPHP6.0.12LTS反序列漏洞分析 - FreeBuf网络安全行业门户 解题过程 ThinkPHP V6.0.12LTS反序列化的链子可以找到,找到反序列化的入口就行 反序列化的入口在index.php/index/test 链子 …...
模型蒸馏笔记
文章目录 一、什么是模型蒸馏二、如何蒸馏三、常见问题3.1 四、参考文献 一、什么是模型蒸馏 Hinton在NIPS2014提出了知识蒸馏(Knowledge Distillation)的概念,旨在把一个大模型或者多个模型ensemble学到的知识迁移到另一个轻量级单模型上&a…...
HAL库使用FreeRTOS实时操作系统时配置时基源(TimeBase Source)
需要另外的定时器,用systic的时候生成项目会有警告 https://blog.51cto.com/u_16213579/10967728...
如何让你的网站能通过域名访问
背景 当我们租一台云服务器,并在上面运行了一个Web服务,我们可以使用云服务器的公网IP地址进行访问,如下: 本文主要记录如何 实现让自己的网站可以通过域名访问。 买域名 可以登录腾讯云等主流公有云平台的,购买域名…...
Spring Boot + Spring Security + JWT 从零开始
Spring Boot + Spring Security + JWT 从零开始 这篇笔记中,我们将学习如何从头开始设置一个带有Spring Security的Spring Boot应用程序,它连接到一个LDAP身份验证的Spring Security身份验证提供程序,这将是即将出现的,这个连接和工作都是开箱即用的。 实际上,设置这个非…...
【busybox记录】【shell指令】rmdir
目录 内容来源: 【GUN】【rmdir】指令介绍 【busybox】【rmdir】指令介绍 【linux】【rmdir】指令介绍 使用示例: 删除空目录 - 默认 删除dirname下的所有空目录,包括因删除其他目录而变为空的目录 常用组合指令: 指令不…...
[LitCTF 2023]yafu (中级) (素数分解)
题目: from Crypto.Util.number import * from secret import flagm bytes_to_long(flag) n 1 for i in range(15):n *getPrime(32) e 65537 c pow(m,e,n) print(fn {n}) print(fc {c})n 152412082177688498871800101395902107678314310182046454156816957…...
MySQL alter 语句
ALTER TABLE user ADD COLUMN cdkey varchar(255) CHARACTER SET utf8mb4 COLLATE utf8mb4_bin NULL DEFAULT NULL COMMENT CD-Key, ADD COLUMN erp_userid varchar(255) CHARACTER SET utf8mb4 COLLATE utf8mb4_bin NULL DEFAULT NULL COMMENT ERP用户ID, ADD UNIQUE INDEX un…...
未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?
编辑:陈萍萍的公主一点人工一点智能 未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战,在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...
C++初阶-list的底层
目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...
Debian系统简介
目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版ÿ…...
STM32+rt-thread判断是否联网
一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...
(二)TensorRT-LLM | 模型导出(v0.20.0rc3)
0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述,后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作,其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...
2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面
代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口(适配服务端返回 Token) export const login async (code, avatar) > {const res await http…...
高危文件识别的常用算法:原理、应用与企业场景
高危文件识别的常用算法:原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件,如包含恶意代码、敏感数据或欺诈内容的文档,在企业协同办公环境中(如Teams、Google Workspace)尤为重要。结合大模型技术&…...
从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)
设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile,新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...
css3笔记 (1) 自用
outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size:0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格ÿ…...
安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖
在Vuzix M400 AR智能眼镜的助力下,卢森堡罗伯特舒曼医院(the Robert Schuman Hospitals, HRS)凭借在无菌制剂生产流程中引入增强现实技术(AR)创新项目,荣获了2024年6月7日由卢森堡医院药剂师协会࿰…...
