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

数据结构 - 优先级队列(堆)

文章目录

  • 前言
  • 1.介绍优先级队列
  • 2. 认识堆
  • 3. 实现优先级队列
    • 3.1 了解优先级队列的构造方法:
    • 3.2 使用优先级队列解决问题:
  • 总结


前言

本篇PriorityQueue优先级队列的介绍其底层是堆,关于堆的认识,使用优先级队列能解决的一些问题;如有错误,请在评论区指正,让我们一起交流,共同进步!


本文开始

1.介绍优先级队列

优先级队列:它的底层是一种堆的数据结构,它以顺序结构存储,是一个一维数组;

既然底层是堆,就来了解一下!

2. 认识堆

认识堆的特点:有两种堆类型
① 小根堆:父节点小于左右孩子节点,不能保证左右孩子谁大; =》使用优先级队列就创建了小根堆,想要创建大根堆需要自己给比较器(根据自定义规则比较,用于节点交换);
② 大根堆:父节点大于左右孩子节点,不能保证左右孩子谁大;
③ 堆还是完全二叉树:可以使用顺序存储;非完全二叉树存储,为了还原二叉树还需要存储空节点,浪费空间 - 》堆为什么可以顺序存储的原有;

代码实现小根堆:
向下调整(父节点向下走):从最后一颗子树开始,父节点与子节点比较大小是否交换,直到不用比较就确定了小根堆;

/*** 建堆的时间复杂度:* O(n)*/
//求出最后一个父节点,因为是顺序存储的-1就是下一颗树的父节点public void createHeap(int[] array) {for (int parent = (usedSize - 1) / 2; parent >= 0; parent--) {//获取最后一个子树父节点,usedSize记录数组中存储的个数//传递父节点和孩子节点最大的范围shiftDown(parent,usedSize);}}/*** root 是每棵子树的根节点的下标*  len  是每棵子树调整结束的结束条件* 向下调整的时间复杂度:O(logn) ;最坏换树的高度*/private void shiftDown(int root,int len) {//向下调整需要每个子树的父节点int child = 2 * root + 1;//求出左孩子节点位置while (child < len) {//获取孩子节点最大值下标//防止右孩子下标越界,需要判断if(child + 1 < len && elem[child] < elem[child + 1]) {child++;}//比较父子节点大小if(elem[child] > elem[root]) {swap(elem,child,root);//调整父子节点下标位置child = root;root = 2 * child + 1;//再次获取左孩子节点下标}else {//父节点大于子节点直接跳出break;}}}//交换函数private void swap(int[] elem, int child, int root) {int tmp = elem[child];elem[child] = elem[root];elem[root] = tmp;}

代码实现大根堆
向上调整(孩子节点向上走):

private void shiftUp(int child) {//求出它的父节点下标int parent = (child - 1) / 2;//child==0最后一个节点不用比较while (child > 0) {//比较父子节点大小if(elem[child] > elem[parent]) {//交换swap(elem,child,parent);//移动父子节点下标,可能不止移动一次(子节点向上)child = parent;parent = (child - 1) / 2;//获得更上一级的父节点下标}else {//父节点小于子节点直接跳出break;}}
}

3. 实现优先级队列

了解大根堆,小根堆就可以实现优先级队列!
代码实现优先级队列(以大根堆为例):

public class PriorityQueue {public int[] elem;public int usedSize;public PriorityQueue() {int[] elem = new int[10];}//交换函数private void swap(int[] elem, int child, int root) {int tmp = elem[child];elem[child] = elem[root];elem[root] = tmp;}/*** 入队:仍然要保持是大根堆*/public void push(int val) {//插入if(isFull()) {//扩增Arrays.copyOf(elem,2*elem.length);return;}//没满就在最后位置插入elem[usedSize] = val;//向上调整即可shiftUp(usedSize);usedSize++;}public boolean isFull() {return usedSize == elem.length;}/*** 出队删除:每次删除的都是优先级高的元素* 仍然要保持是大根堆*/public void pollHeap() {if(isEmpty()) {return;}//交换首尾int end = usedSize - 1;swap(elem,0,end);//向下调整范围需要-1,因为删除了一个元素shiftDown(0,--usedSize);}
//判断是否为空public boolean isEmpty() {return usedSize == 0;}/*** 获取堆顶元素*/public int peekHeap() {if(isEmpty()) {return -1;}return elem[0];}
}

3.1 了解优先级队列的构造方法:

无参构造:默认大小11

在这里插入图片描述

有一个整形参数的构造:

在这里插入图片描述

两个参数(整形,比较规则)的构造

在这里插入图片描述

3.2 使用优先级队列解决问题:

1.top-k问题:
例如取前k个最小 / 最大的值;
2.堆排序
①升序(1,2,3…):大根堆
使用原因:大根堆堆顶元素一定最大的,将堆顶元素与堆末尾元素交换,再向下调整,重新得到大根堆;这样每次都会把最大的放到最后,再次到堆顶的时候,堆顶后面的元素已经有序了,依次弹出即可;
②降序(4,3,2…):小根堆
使用原有:小根堆堆顶元素一定最小的,将堆顶元素与堆末尾元素交换,再向下调整,重新得小根堆;这样每次都会把最小的放到最后,再次到堆顶的时候,堆顶后面的元素已经降序有序了,依次弹出即可;


总结

✨✨✨各位读友,本篇分享到内容如果对你有帮助给个👍赞鼓励一下吧!!
感谢每一位一起走到这的伙伴,我们可以一起交流进步!!!一起加油吧!!!

相关文章:

数据结构 - 优先级队列(堆)

文章目录前言1.介绍优先级队列2. 认识堆3. 实现优先级队列3.1 了解优先级队列的构造方法&#xff1a;3.2 使用优先级队列解决问题&#xff1a;总结前言 本篇PriorityQueue优先级队列的介绍其底层是堆&#xff0c;关于堆的认识&#xff0c;使用优先级队列能解决的一些问题&…...

PDF内容提取器:ByteScout PDF Extractor SDK Crack

ByteScout PDF Extractor SDK – 用于 PDF 到 JSON、PDF 到 Excel、CSV、XML、从 .NET 和 ASP.NET 从 PDF 中提取文本的 PDF 提取器库 ByteScout PDF Extractor SDK – 用于 PDF 到 JSON、PDF 到 Excel、CSV、XML、从 .NET 和 ASP.NET 从 PDF 中提取文本的 PDF 提取器库​ ​ ​…...

字母板上的路径[提取公共代码,提高复用率]

提取公共代码前言一、字母版上的路径二、贪心1、idea2、go3、代码不断拆分复用的过程总结参考文献前言 写代码&#xff0c;在提高效率的同时&#xff0c;要方便人看&#xff0c;这个人包括自己。大函数要拆分成一些小函数&#xff0c;让每个函数的宏观目的和步骤都显得清晰&am…...

c# winform错误大全

c# winform 错误大全为了实现安装包安装完成后&#xff0c;启动程序。System.BadImageFormatException: 未能加载文件或程序集“file:///C:\xxxxxxxxx\xxxxxxx.exe”或它的某一个依赖项。生成此程序集的运行时比当前加载的运行时新&#xff0c;无法加载此程The version of the …...

AI_News周刊:第一期

2023.02.06—2023.02.12 关于ChatGPT的前言&#xff1a; 在去年年末&#xff0c;OpenAI的ChatGPT在技术圈已经火了一次&#xff0c;随着上周它的二次出圈&#xff0c;ChatGPT算得上是人工智能领域的一颗明星&#xff0c;它在聊天机器人领域有着不可忽视的影响力。其准确、快速…...

搭建mysql主从复制

前言&#xff1a; &#x1f44f; 作者简介&#xff1a;我是笑霸final&#xff0c;一名热爱技术的在校学生。 &#x1f4dd; 个人主页&#xff1a;个人主页1 || 笑霸final的主页2 &#x1f4d5; 系列专栏&#xff1a;数据库 &#x1f4e7; 如果文章知识点有错误的地方&#xff0…...

内存溢出、内存泄露的概述及常见情形

内存溢出&#xff08;OutofMemoryError&#xff09; 简述 java doc 中对 Out Of Memory Error 的解释是&#xff0c;没有空闲内存&#xff0c;并且垃圾收集器也无法提供更多内存。 JVM 提供的内存管理机制和自动垃圾回收极大的解放了用户对于内存的管理&#xff0c;由于 GC&…...

Linux 中断实验

目录 一、Linux 中断简介 上半部与下半部 二、添加设备树 三、编写驱动 1、定义宏 2、编写一个key结构体 3、imx6uirq设备添加成员 ​编辑4、按键中断处理函数 5、按键初始化 6、在驱动入口添加初始化 7、 驱动出口函数 代码如下 四、利用定时器进行消抖处理 1、添…...

【c++】指针

文章目录指针的定义和使用指针所占的内存空间空指针野指针const修饰指针指针和数组指针和函数指针、数组、函数案例&#xff1a;冒泡排序指针的定义和使用 指针定义的语法&#xff1a;数据类型 * 指针变量名 使用指针&#xff1a; 可以通过解引用的方式来找到指针指向的内存&…...

别具一格的婚礼,VR全景+婚礼的优势展现在哪里?

随着90后、95后逐渐步入结婚的主力军中&#xff0c;如何策划一场别具一格的婚礼是许多年轻人所头疼的&#xff0c;那么今年我们就可以玩点新潮的&#xff0c;VR婚礼或许是个不错的选择。 VR全景婚礼就是通过全景摄像机对婚礼进行记录&#xff0c;不但可以帮助新人捕捉婚礼的精彩…...

【GD32F427开发板试用】5. SPI驱动TFTLCD屏幕

本篇文章来自极术社区与兆易创新组织的GD32F427开发板评测活动&#xff0c;更多开发板试用活动请关注极术社区网站。作者&#xff1a;hehung 之前发帖 【GD32F427开发板试用】1. 串口实现scanf输入控制LED 【GD32F427开发板试用】2. RT-Thread标准版移植 【GD32F427开发板试用…...

测试2年还拿实习生的薪资打发我,你后悔去吧····

20年7月大学毕业&#xff0c;学的计算机科学专业。因为考研之后&#xff0c;秋招结束了。没什么更多的岗位选择&#xff0c;就想找个工作先干着&#xff0c;然后亲戚在一家大厂公司上班说要招测试&#xff0c;所以就来做测试了。 虽然都是属于计算机大类&#xff0c;但自己专业…...

面向对象程序(C++)设计基础

一、类&对象C 在 C 语言的基础上增加了面向对象编程&#xff0c;C 支持面向对象程序设计。类是 C 的核心特性&#xff0c;通常被称为用户定义的类型。类提供了对象的蓝图&#xff0c;所以基本上&#xff0c;对象是根据类来创建的。声明类的对象&#xff0c;就像声明基本类型…...

conda安装nodejs版本过低解决方法

conda命令直接安装nodejs时&#xff0c;可能会由于镜像源中nodejs版本过低导致没法安装高本版的nodejs&#xff0c;导致无法jupyterlab使用一些扩展插件。 解决方法如下&#xff1a;&#xff08;windows环境下直接按提示下载版本安装就行&#xff0c;此处只介绍linux环境的解决…...

前端工程师leetcode算法面试必备-二分搜索算法(下)索算法(下)

一、287. 寻找重复数 给定一个包含 n 1 个整数的数组 nums&#xff0c;其数字都在 1 到 n 之间&#xff08;包括 1 和 n&#xff09;&#xff0c;可知至少存在一个重复的整数。假设只有一个重复的整数&#xff0c;找出这个重复的数。 1、HashMap 在没有其它附加条件的情况下&…...

使用Autowired为什么会被IDEA警告,应该怎么修改最佳

问题原因 关于这个问题&#xff0c;其实答案相对统一&#xff0c;实际上用大白话说起来也容易理解。 初始化问题 先看一下Java初始化类的顺序&#xff1a;父类的静态字段 > 父类静态代码块 > 子类静态字段 > 子类静态代码块 > 父类成员变量 > 父类构造代码块 &…...

面向对象(中)

面向对象&#xff08;中&#xff09; 一、 面向对象之继承性 继承性的好处 减少代码的冗余&#xff0c;提高了代码的复用性。 便于功能的扩展。 为多态性的使用&#xff0c;提供了前提。 继承性的格式 class A extends B{} A&#xff1a;子类、派生类、subclass B&#xff1a…...

【云原生】promehtheus整合grafana实现可视化监控实战

文章目录前言一. 实验环境二. 安装grafana2.1 grafana的介绍2.2 为什么选择grafana&#xff1f;2.3 grafana下载及安装三. 网页端配置grafana3.1 浏览器访问grafana网页3.2 使用grafana 获取prometheus的数据源3.3 grafana导入prometheus模板总结前言 大家好&#xff0c;又见面…...

Linux 内核定时器实验

目录 一、内核时间管理简介 二、内核定时器简介 三、驱动编写 1、修改makefile 2、添加定义 3、初始化led函数 4、添加调用 5、初始化定时器与定时器处理函数 这部分代码如下 四、ioctl函数 五、内核添加unlocked_ioctl 函数 1、添加设备操作集unlocked_ioctl成员 2…...

喜欢大屏电视?那就选择酷开系统,实现智能生活享受

随着科技的发展和我们生活水平的提高&#xff0c;越来越多的消费者开始认可并习惯使用各种高质量的科技产品&#xff0c;比如喜欢玩游戏的消费者&#xff0c;他们往往会追求流畅性更强、刷新率更快的大显示屏&#xff0c;以此获得更真实刺激的游戏体验&#xff0c;而喜欢追剧的…...

React Native 开发环境搭建(全平台详解)

React Native 开发环境搭建&#xff08;全平台详解&#xff09; 在开始使用 React Native 开发移动应用之前&#xff0c;正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南&#xff0c;涵盖 macOS 和 Windows 平台的配置步骤&#xff0c;如何在 Android 和 iOS…...

江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命

在华东塑料包装行业面临限塑令深度调整的背景下&#xff0c;江苏艾立泰以一场跨国资源接力的创新实践&#xff0c;重新定义了绿色供应链的边界。 跨国回收网络&#xff1a;废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点&#xff0c;将海外废弃包装箱通过标准…...

Matlab | matlab常用命令总结

常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...

数据库分批入库

今天在工作中&#xff0c;遇到一个问题&#xff0c;就是分批查询的时候&#xff0c;由于批次过大导致出现了一些问题&#xff0c;一下是问题描述和解决方案&#xff1a; 示例&#xff1a; // 假设已有数据列表 dataList 和 PreparedStatement pstmt int batchSize 1000; // …...

GC1808高性能24位立体声音频ADC芯片解析

1. 芯片概述 GC1808是一款24位立体声音频模数转换器&#xff08;ADC&#xff09;&#xff0c;支持8kHz~96kHz采样率&#xff0c;集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器&#xff0c;适用于高保真音频采集场景。 2. 核心特性 高精度&#xff1a;24位分辨率&#xff0c…...

初探Service服务发现机制

1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能&#xff1a;服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源&#xf…...

C++课设:简易日历程序(支持传统节假日 + 二十四节气 + 个人纪念日管理)

名人说:路漫漫其修远兮,吾将上下而求索。—— 屈原《离骚》 创作者:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 专栏介绍:《编程项目实战》 目录 一、为什么要开发一个日历程序?1. 深入理解时间算法2. 练习面向对象设计3. 学习数据结构应用二、核心算法深度解析…...

02.运算符

目录 什么是运算符 算术运算符 1.基本四则运算符 2.增量运算符 3.自增/自减运算符 关系运算符 逻辑运算符 &&&#xff1a;逻辑与 ||&#xff1a;逻辑或 &#xff01;&#xff1a;逻辑非 短路求值 位运算符 按位与&&#xff1a; 按位或 | 按位取反~ …...

土建施工员考试:建筑施工技术重点知识有哪些?

《管理实务》是土建施工员考试中侧重实操应用与管理能力的科目&#xff0c;核心考查施工组织、质量安全、进度成本等现场管理要点。以下是结合考试大纲与高频考点整理的重点内容&#xff0c;附学习方向和应试技巧&#xff1a; 一、施工组织与进度管理 核心目标&#xff1a; 规…...

CppCon 2015 学习:Time Programming Fundamentals

Civil Time 公历时间 特点&#xff1a; 共 6 个字段&#xff1a; Year&#xff08;年&#xff09;Month&#xff08;月&#xff09;Day&#xff08;日&#xff09;Hour&#xff08;小时&#xff09;Minute&#xff08;分钟&#xff09;Second&#xff08;秒&#xff09; 表示…...