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

用大顶堆和小顶堆实现优先队列

大顶堆小顶堆(或大根堆小根堆)

利用大顶堆实现优先队列,所谓大顶堆,容器内部元素是有序的,而且是按从大到小排序的(小顶堆刚好相反,从小到大)。容器只有一个出口一个入口,将元素放进去之后大顶堆会自动对其进行排序,大顶堆最大的元素放在对顶(小顶堆最小元素在对顶),堆顶元素弹出后,下一个最大(或最小)的元素作堆顶。

c++的实现如下:

//构造一个空的优先队列priority_queue<int>head;//(c++默认为大顶堆)
//构造一个大顶堆priority_queue<int, vector<int>,less<int>> max_head;
//构造一个小顶堆priority_queue<int, vector<int>,greater<int>>min_head;
//第一个参数为要插入的元素类型,第二个参数为实现优先队列的底层容器,
//第三个参数为比较规则,less为大顶堆的规则,greater为小顶堆,
//系统自动实现,也可以自定义排序规则
//后两个可以省略,第一个参数不能省略自定义排序规则:
static bool cmp(const pair<int,int>& a, const pair<int,int>& b) {return a.first == b.first ? (a.second - b.second) : (a.first - b.first);
}priority_queue<pair<int,int>, vector<pair<int,int>>,cmp>pri_que;
//优先队列中存放的是一对整数,按照第一个元素升序排序,如果第一个元素相同比较第二个元素  
常见成员函数:
boolemploy()

返回值为true说明队列为空。

intsize()

返回优先队列里的元素数量。

voidpop()

删除队列顶部元素。

inttop()

返回队列顶部元素,但不删除该元素。

voidpush(int value)

将元素value插入队列中。

java的实现方法:

PriorityQueue<Integer>head = new PriorityQueue<>();//注意java默认是小顶堆
//如果需要大顶堆需要自己提供比较器
class MyCmp implements Comparator<Integer>{@Overridepublic int compare(Integer o1,Integer o1) {return o2 - o1;}
}
PriorityQueue<Integer>head = new PriorityQueue<>(new MyCmp);
    • 一些常用的方法:
    • booleanadd(E e)

      将指定的元素插入到此优先级队列中。

      voidclear()

      从此优先级队列中删除所有元素。

      booleancontains(Object o)

      如果此队列包含指定的元素,则返回 true

      Epeek()

      检索但不删除此队列的头,如果此队列为空,则返回 null

      Epoll()

      检索并删除此队列的头,如果此队列为空,则返回 null

      booleanremove(Object o)

      从该队列中删除指定元素的单个实例(如果存在)。

      intsize()

      返回此集合中的元素数。

      Object[]toArray()

      返回一个包含此队列中所有元素的数组。

总结

优先队列是一种比较重要的数据结构,可以以O(logn)的效率来增减元素,主要运用于排序。

相关文章:

用大顶堆和小顶堆实现优先队列

大顶堆小顶堆&#xff08;或大根堆小根堆&#xff09; 利用大顶堆实现优先队列&#xff0c;所谓大顶堆&#xff0c;容器内部元素是有序的&#xff0c;而且是按从大到小排序的&#xff08;小顶堆刚好相反&#xff0c;从小到大&#xff09;。容器只有一个出口一个入口&#xff0…...

PDCA项目开发环境搭建说明

PDCA项目开发环境搭建说明 环境准备 JDK 15.0 &#xff1b; IDEA Community Edition 2021.3 版本要对应&#xff0c;不然会报错 Jdk 安装步骤&#xff1a;https://blog.csdn.net/qq_34913677/article/details/108894727 IDea 安装说明&#xff1a;https://blog.csdn.net/dream…...

Git简明教程

1.Git的定位 在我们自己开发项目的过程中&#xff0c;经常会遇到这样的情况&#xff0c;为了防止代码丢失&#xff0c;或者新变更的代码影响到原有的代码功能&#xff0c;为了在失误后能恢复到原来的版本&#xff0c;不得不复制出一个副本,比如&#xff1a;“坦克大战1.0”“坦…...

数据结构顺序表(C语言版)

目录 1.实现的接口及其功能2.代码块 1.实现的接口及其功能 //初始化顺序表void initSL(SL* p); //销毁顺序表 void DestorySL(SL* p); //头插 void PushFont(SL* p, SeqListType x); //尾插 void PushBack(SL* p, SeqListType x); //头删 void PopFont(SL* p); //尾删 void Pop…...

新手如何备考学习PMP?

一、PMP学习7步走攻略 1、熟悉考试大纲&#xff1a; PMP考试大纲是备考的基础&#xff0c;考生需要详细熟悉考试大纲&#xff0c;了解各个知识领域的重点和难点。 2、制定学习计划&#xff1a; 根据考试大纲和个人情况&#xff0c;制定学习计划&#xff0c;合理分配学习时间…...

[卷积神经网络]FasterNet论文解析

一、概述 FasterNet是CVPR2023的文章&#xff0c;通过使用全新的部分卷积PConv&#xff0c;更高效的提取空间信息&#xff0c;同时削减冗余计算和内存访问&#xff0c;效果非常明显。相较于DWConv&#xff0c;PConv的速度更快且精度也非常高&#xff0c;识别精度基本等同于大型…...

知识图谱+推荐系统 文献阅读

文献阅读及整理 知识图谱推荐系统 知识图谱 1 基于知识图谱的电商领域智能问答系统研究与实现 [1]蒲海坤. 基于知识图谱的电商领域智能问答系统研究与实现[D].西京学院,2022.DOI:10.27831/d.cnki.gxjxy.2021.000079. 知识点 BIO标记策略进行人工标记,构建了电商领域商品…...

shell_39.Linux参数测试

参数测试 在 shell 脚本中使用命令行参数时要当心。如果运行脚本时没有指定所需的参数&#xff0c;则可能会出问题&#xff1a; $ ./positional1.sh ./positional1.sh: line 5: ((: number < : syntax error: operand expected (error token is "< ") The …...

3D模型格式转换工具HOOPS Exchange助力SIMCON搭建注塑项目

行业&#xff1a;设计与制造 / 注塑成型 / 模拟 挑战&#xff1a;注塑成型商面临着以高效的方式为客户生产零件的挑战。需要大量的试验才能生产出适合的零件&#xff0c;同时模具需要进行多次物理修改&#xff0c;每次修改周期最长需要四个星期&#xff0c;成本高达四到五位数…...

Linux_虚拟内存机制

虚拟内存是如何工作的 我们的程序中使用的所有地址都是虚拟地址&#xff0c;但实际数据是从磁盘空间缓存在物理内存中&#xff0c;读的还是内存中的数据&#xff0c;所以每次CPU的访存操作都会先将虚拟内存交给CPU中的MMU硬件&#xff0c;利用存在主存&#xff08;实际也可能在…...

淘宝官方开放平台API接口获得店铺的所有商品、商品id、商品标题、销量参数调用示例

在电商平台中&#xff0c;获取店铺所有商品是一个非常常见的需求。这个功能允许用户一次性获取指定店铺中的所有商品信息&#xff0c;方便用户对店铺的商品进行浏览和筛选。下面将对获取店铺所有商品接口的功能进行介绍。 获取全部商品信息&#xff1a;通过调用获取店铺所有商…...

Java Spring 通过 AOP 实现方法参数的重新赋值、修改方法参数的取值

AOP 依赖 我创建的项目项目为 SpringBoot 项目 <parent><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-parent</artifactId><version>3.1.3</version></parent><dependency><groupId…...

Real3D FlipBook jQuery Plugin 3.41 Crack

Real3D FlipBook 和 PDF 查看器 jQuery 插件 - CodeCanyon 待售物品 实时预览 截图 视频预览 Real3D Flipbook jQuery 插件 - 1 Real3D Flipbook jQuery 插件 - 2 Real3D Flipbook jQuery 插件 - 3 新功能 – REAL3D FLIPBOOK JQUERY 插件的 PDF 到图像转换器 一款用于将…...

Pytorch:model.train()和model.eval()用法和区别,以及model.eval()和torch.no_grad()的区别

1 model.train() 和 model.eval()用法和区别 1.1 model.train() model.train()的作用是启用 Batch Normalization 和 Dropout。 如果模型中有BN层(Batch Normalization&#xff09;和Dropout&#xff0c;需要在训练时添加model.train()。model.train()是保证BN层能够用到每一…...

Linux CentOS 8(firewalld的配置与管理)

Linux CentOS 8&#xff08;firewalld的配置与管理&#xff09; 目录 一、firewalld 简介二、firewalld 工作概念1、预定义区域&#xff08;管理员可以自定义修改&#xff09;2、预定义服务 三、firewalld 配置方法1、通过firewall-cmd配置2、通过firewall图形界面配置 四、配置…...

C复习-指针

参考&#xff1a; 里科《C和指针》 指针存储的是一个地址&#xff0c;实际就是一个值。 如果像下面一样对未初始化的指针进行赋值&#xff0c;如果a的初始值是非法地址&#xff0c;那么会报错。UNIX会提示段错误segmentation violation&#xff0c;或内存错误memory fault&…...

Runnable和Thread的区别,以及如何调用start()方法

Runnable和Thread都是Java多线程编程中的核心概念&#xff0c;它们之间存在以下主要差异&#xff1a; Runnable是一个接口&#xff0c;而Thread是一个类。这意味着我们可以通过实现Runnable接口来创建线程&#xff0c;或者直接继承Thread类并重写其方法。Runnable只包含一个ru…...

云音乐Android Cronet接入实践

背景 网易云音乐产品线终端类型广泛&#xff0c;除了移动端&#xff08;IOS/安卓&#xff09;之外&#xff0c;还有PC、MAC、Iot多终端等等。移动端由于上线时间早&#xff0c;用户基数大&#xff0c;沉淀了一些端侧相对比较稳定的网络策略和网络基础能力。然而由于各端在基础…...

Linux dup和dup2

Linux dup和dup2函数&#xff0c;他们有什么区别&#xff0c;什么场景下会用到&#xff0c;使用它们有什么注意事项 dup和dup2都是Linux系统中的系统调用&#xff0c;用于复制文件描述符。它们的主要区别在于如何指定新的文件描述符以及处理新文件描述符的方式。 dup函数 #i…...

Spring Boot实战 | 如何整合高性能数据库连接池HikariCP

专栏集锦&#xff0c;大佬们可以收藏以备不时之需 Spring Cloud实战专栏&#xff1a;https://blog.csdn.net/superdangbo/category_9270827.html Python 实战专栏&#xff1a;https://blog.csdn.net/superdangbo/category_9271194.html Logback 详解专栏&#xff1a;https:/…...

观成科技:隐蔽隧道工具Ligolo-ng加密流量分析

1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具&#xff0c;该工具基于TUN接口实现其功能&#xff0c;利用反向TCP/TLS连接建立一条隐蔽的通信信道&#xff0c;支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式&#xff0c;适应复杂网…...

visual studio 2022更改主题为深色

visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中&#xff0c;选择 环境 -> 常规 &#xff0c;将其中的颜色主题改成深色 点击确定&#xff0c;更改完成...

蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练

前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1)&#xff1a;从基础到实战的深度解析-CSDN博客&#xff0c;但实际面试中&#xff0c;企业更关注候选人对复杂场景的应对能力&#xff08;如多设备并发扫描、低功耗与高发现率的平衡&#xff09;和前沿技术的…...

MODBUS TCP转CANopen 技术赋能高效协同作业

在现代工业自动化领域&#xff0c;MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步&#xff0c;这两种通讯协议也正在被逐步融合&#xff0c;形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...

RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文全面剖析RNN核心原理&#xff0c;深入讲解梯度消失/爆炸问题&#xff0c;并通过LSTM/GRU结构实现解决方案&#xff0c;提供时间序列预测和文本生成…...

dify打造数据可视化图表

一、概述 在日常工作和学习中&#xff0c;我们经常需要和数据打交道。无论是分析报告、项目展示&#xff0c;还是简单的数据洞察&#xff0c;一个清晰直观的图表&#xff0c;往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server&#xff0c;由蚂蚁集团 AntV 团队…...

算法笔记2

1.字符串拼接最好用StringBuilder&#xff0c;不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...

10-Oracle 23 ai Vector Search 概述和参数

一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI&#xff0c;使用客户端或是内部自己搭建集成大模型的终端&#xff0c;加速与大型语言模型&#xff08;LLM&#xff09;的结合&#xff0c;同时使用检索增强生成&#xff08;Retrieval Augmented Generation &#…...

消防一体化安全管控平台:构建消防“一张图”和APP统一管理

在城市的某个角落&#xff0c;一场突如其来的火灾打破了平静。熊熊烈火迅速蔓延&#xff0c;滚滚浓烟弥漫开来&#xff0c;周围群众的生命财产安全受到严重威胁。就在这千钧一发之际&#xff0c;消防救援队伍迅速行动&#xff0c;而豪越科技消防一体化安全管控平台构建的消防“…...

嵌入式学习之系统编程(九)OSI模型、TCP/IP模型、UDP协议网络相关编程(6.3)

目录 一、网络编程--OSI模型 二、网络编程--TCP/IP模型 三、网络接口 四、UDP网络相关编程及主要函数 ​编辑​编辑 UDP的特征 socke函数 bind函数 recvfrom函数&#xff08;接收函数&#xff09; sendto函数&#xff08;发送函数&#xff09; 五、网络编程之 UDP 用…...