当前位置: 首页 > 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:/…...

Vim 调用外部命令学习笔记

Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...

测试微信模版消息推送

进入“开发接口管理”--“公众平台测试账号”&#xff0c;无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息&#xff1a; 关注测试号&#xff1a;扫二维码关注测试号。 发送模版消息&#xff1a; import requests da…...

8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂

蛋白质结合剂&#xff08;如抗体、抑制肽&#xff09;在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上&#xff0c;高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术&#xff0c;但这类方法普遍面临资源消耗巨大、研发周期冗长…...

安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件

在选煤厂、化工厂、钢铁厂等过程生产型企业&#xff0c;其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进&#xff0c;需提前预防假检、错检、漏检&#xff0c;推动智慧生产运维系统数据的流动和现场赋能应用。同时&#xff0c;…...

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

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

DBAPI如何优雅的获取单条数据

API如何优雅的获取单条数据 案例一 对于查询类API&#xff0c;查询的是单条数据&#xff0c;比如根据主键ID查询用户信息&#xff0c;sql如下&#xff1a; select id, name, age from user where id #{id}API默认返回的数据格式是多条的&#xff0c;如下&#xff1a; {&qu…...

ElasticSearch搜索引擎之倒排索引及其底层算法

文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...

【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)

升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点&#xff0c;但无自动故障转移能力&#xff0c;Master宕机后需人工切换&#xff0c;期间消息可能无法读取。Slave仅存储数据&#xff0c;无法主动升级为Master响应请求&#xff…...

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南

&#x1f680; C extern 关键字深度解析&#xff1a;跨文件编程的终极指南 &#x1f4c5; 更新时间&#xff1a;2025年6月5日 &#x1f3f7;️ 标签&#xff1a;C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言&#x1f525;一、extern 是什么&#xff1f;&…...

用docker来安装部署freeswitch记录

今天刚才测试一个callcenter的项目&#xff0c;所以尝试安装freeswitch 1、使用轩辕镜像 - 中国开发者首选的专业 Docker 镜像加速服务平台 编辑下面/etc/docker/daemon.json文件为 {"registry-mirrors": ["https://docker.xuanyuan.me"] }同时可以进入轩…...