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

《Java初阶数据结构》----6.<优先级队列之PriorityQueue底层:堆>

前言

      大家好,我目前在学习java。之前也学了一段时间,但是没有发布博客。时间过的真的很快。我会利用好这个暑假,来复习之前学过的内容,并整理好之前写过的博客进行发布。如果博客中有错误或者没有读懂的地方。热烈欢迎大家在评论区进行讨论!!!

      喜欢我文章的兄弟姐妹们可以点赞,收藏和评论我的文章。喜欢我的兄弟姐妹们以及也想复习一遍java知识的兄弟姐妹们可以关注我呦,我会持续更新滴,
     望支持!!!!!!一起加油呀!!!!

语言只是工具,不能决定你好不好找工作,决定你好不好找工作的是你的能力!!!!!

学历本科及以上就够用了!!!!!!!!!!!!!!!!!!!!!!


本篇博客主要讲解Java基础语法中的

堆的概念及实现、堆的性质、堆的创建、堆的插入与删除、堆的应用。

下一篇文章我们会重点将优先级队列


一、优先级队列

1.1什么是优先级队列

        前面我们了解过队列是一种先进先出(FIFO)的数据结构。但有些情况下,操作的数据可能带有优先级,一般出队列时,可能需要优先级高的元素先出队列。此时普通队列就不适用了。因此我们引入优先级队列。

数据结构应该提供两个最基本的操作,一个是返回最高优先级对象一个是添加新的对象。这种数据结构就是优先级队列(Priority Queue)。

 1.2优先级队列的实现

JDK1.8中的PriorityQueue底层使用了这种数据结构

堆:实际就是在完全二叉树的基础上进行了一些调整。

二、堆

2.1堆的概念 

如果有一个关键码的集合K = {k0,k1, k2,…,kn-1},把它的所有元素按完全二叉树的顺序存储方式存储在一 个一维数组中,并满足: Ki <=  K2i+1 且 Ki <= K2i+2( Ki >=  K2i+1 且 Ki >= K2i+2) i = 0,1,2…,则称为 小堆(或大堆)。将根节点最大的堆叫做最大堆大根堆,根节点最小的堆叫做最小堆小根堆

2.2堆的性质

堆的性质:

  • 堆中某个节点的值总是不大于或不小于其父节点的值;
  • 堆总是一棵完全二叉树。 

2.3 堆的存储方式

从堆的概念可知,堆是一棵完全二叉树,因此可以层序的规则采用顺序的方式来高效存储, 

注意:对于非完全二叉树,则不适合使用顺序方式进行存储,因为为了能够还原二叉树,空间中必须要存储空节 点,就会导致空间利用率比较低。

将元素存储到数组中后,可以根据二叉树章节的性质5对树进行还原。假设i为节点在数组中的下标,则有:

  • 如果i为0,则i表示的节点为根节点,否则i节点的双亲节点为 (i - 1)/2
  • 如果2 * i + 1 小于节点个数,则节点i的左孩子下标为2 * i + 1,否则没有左孩子
  • 如果2 * i + 2 小于节点个数,则节点i的右孩子下标为2 * i + 2,否则没有右孩子 

2.4 堆的创建

2.4.1 堆向下调整

根节点的左右子树满足堆的特性(创建堆)

对于集合{ 27,15,19,18,28,34,65,49,25,37 }中的数据,如果将其创建成堆呢?

仔细观察上图后发现:根节点的左右子树已经完全满足堆的性质,因此只需将根节点向下调整好即可。

向下过程(以小堆为例):

1. 让parent标记需要调整的节点,child标记parent的左孩子(注意:parent如果有孩子一定先是有左孩子)

2. 如果parent的左孩子存在,即:child < size, 进行以下操作,直到parent的左孩子不存在

parent右孩子是否存在,存在找到左右孩子中最小的孩子,让child进行标

将parent与较小的孩子child比较,

如果:

  • parent小于较小的孩子child,调整结束
  • 否则:交换parent与较小的孩子child,交换完成之后,parent中大的元素向下移动,可能导致子 树不满足对的性质,因此需要继续向下调整,即parent = child;child = parent*2+1; 然后继续2。

代码实现

public void shiftDown(int[] array, int parent) {// child先标记parent的左孩子,因为parent可能右左没有右int child = 2 * parent + 1;int size = array.length;while (child < size) {// 如果右孩子存在,找到左右孩子中较小的孩子,用child进行标记if(child+1 < size && array[child+1] < array[child]){child += 1;}// 如果双亲比其最小的孩子还小,说明该结构已经满足堆的特性了if (array[parent] <= array[child]) {break;}else{// 将双亲与较小的孩子交换int t = array[parent];array[parent] = array[child];array[child] = t;// parent中大的元素往下移动,可能会造成子树不满足堆的性质,因此需要继续向下调整parent = child;child = parent * 2 + 1;}}
}

注意:在调整以parent为根的二叉树时,必须要满足parent的左子树和右子树已经是堆了才可以向下调整。 时间复杂度分析:

最坏的情况即图示的情况,从根一路比较到叶子,比较的次数为完全二叉树的高度,即时间复杂度为O(logN)  

2.4.2根节点的左右子树不满足堆的特性(创建堆)

那对于普通的序列{ 1,5,3,8,7,6 },即根节点的左右子树不满足堆的特性,又该如何调整呢?

代码示例 

public static void createHeap(int[] array) {// 找倒数第一个非叶子节点,从该节点位置开始往前一直到根节点,遇到一个节点,应用向下调整int root = ((array.length-2)>>1);for (; root >= 0; root--) {shiftDown(array, root);}
}

2.4.3 建堆的时间复杂度 

因为堆是完全二叉树,而满二叉树也是完全二叉树,此处为了简化使用满二叉树来证明(时间复杂度本来看的就是 近似值,多几个节点不影响最终结果):

因此:建堆的时间复杂度为O(N)。

2.5 堆的插入与删除

2.5.1 堆的插入

堆的插入总共需要两个步骤:

1. 先将元素放入到底层空间中(注意:空间不够时需要扩容)

2. 将最后新插入的节点向上调整,直到满足堆的性质

代码实现

public void shiftUp(int child) {// 找到child的双亲int parent = (child - 1) / 2;while (child > 0) {// 如果双亲比孩子大,parent满足堆的性质,调整结束if (array[parent] > array[child]) {break;}else{// 将双亲与孩子节点进行交换 int t = array[parent];array[parent] = array[child];array[child] = t;// 小的元素向下移动,可能到值子树不满足对的性质,因此需要继续向上调增child = parent;parent = (child - 1) / 1;}}
}

2.5.2 堆的删除 

注意:堆的删除一定删除的是堆顶元素。具体如下:

1. 将堆顶元素对堆中最后一个元素交换

2. 将堆中有效数据个数减少一个

3. 对堆顶元素进行向下调整

2.5用堆模拟优先级队列

public class MyPriorityQueue {// 演示作用,不再考虑扩容部分的代码private int[] array = new int[100];private int size = 0;public void offer(int e) {array[size++] = e;shiftUp(size - 1);}public int poll() {int oldValue = array[0];array[0] = array[--size];shiftDown(0);return oldValue;}public int peek() {return array[0];}
}

三、堆的应用

3.1 PriorityQueue的实现

用堆作为底层结构封装优先级队列

3.2 堆排序

堆排序即利用堆的思想来进行排序,总共分为两个步骤:

①建堆

升序:建大堆

降序:建小堆

②利用堆删除思想来进行排序

建堆和堆删除中都用到了向下调整,因此掌握了向下调整,就可以完成堆排序。

相关文章:

《Java初阶数据结构》----6.<优先级队列之PriorityQueue底层:堆>

前言 大家好&#xff0c;我目前在学习java。之前也学了一段时间&#xff0c;但是没有发布博客。时间过的真的很快。我会利用好这个暑假&#xff0c;来复习之前学过的内容&#xff0c;并整理好之前写过的博客进行发布。如果博客中有错误或者没有读懂的地方。热烈欢迎大家在评论区…...

Matrix Equation(高斯线性异或消元+bitset优化)

题目&#xff1a; 登录—专业IT笔试面试备考平台_牛客网 思路&#xff1a; 我们发现对于矩阵C可以一列一列求。 mod2&#xff0c;当这一行相乘1的个数为奇数时&#xff0c;z(i,j)为1&#xff0c;偶数为0&#xff0c;是异或消元。 对于b[i&#xff0c;j]*c[i,j],b[i,j]可以…...

【一图学技术】2.API测试9种方法图解

9种API测试方法 冒烟测试&#xff1a;冒烟测试是一种快速的表面级测试&#xff0c;用于验证软件的基本功能是否正常工作&#xff0c;以确定是否值得进行更详细的测试。功能测试&#xff1a;功能测试是验证软件是否符合预期功能要求的测试类型。它涉及对每个功能进行测试&#…...

力扣刷题----42. 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图&#xff0c;计算按此排列的柱子&#xff0c;下雨之后能接多少雨水。 输入&#xff1a;height [0,1,0,2,1,0,1,3,2,1,2,1] 输出&#xff1a;6 解释&#xff1a;上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图&#xf…...

【论文精读】 | 基于图表示的视频抑郁症识别的两阶段时间建模框架

文章目录 0、Description1、Introduction2、Related work2.1 Relationship between depression and facial behaviours2.2 Video-based automatic depression analysis2.3 Facial graph representation 3、The proposed two-stage approach3.1 Short-term depressive behaviour…...

采集PCM,将base64片段转换为wav音频文件

需求 开始录音——监听录音数据——结束录音 在监听录音数据过程中&#xff1a;客户端每100ms给前端传输一次数据&#xff08;pcm数据转成base64&#xff09;&#xff0c;前端需要将base64片段解码、合并、添加WAV头、转成File、上传到 OSS之后将 url 给到服务端处理。 {num…...

eclipse ui bug

eclipse ui bug界面缺陷&#xff0c;可能项目过多&#xff0c;特别maven项目过多&#xff0c;下载&#xff0c;自动编译&#xff0c;加载更新界面异常 所有窗口死活Restore不回去了 1&#xff09;尝试创建项目&#xff0c;还原界面&#xff0c;失败 2&#xff09;关闭所有窗口&…...

前端获取blob文件格式的两种格式

第一种,后台传递给前台是base64格式的JSON数据 这时候前台拿到base64格式的数据可以通过内置的atob解码方法结合new Uint8Array和new Blob方法转换成blob类型的数据格式,然后可以使用blob数据格式进行操作,虽然base64转换成blob要经过很多步骤,但幸运的是这些步骤都是固定的,因…...

向日葵RCE复现(CNVD-2022-10270/CNVD-2022-03672)

一、环境 1.1 网上下载低版本的向日葵<2022 二、开始复现 2.1 在目标主机上打开旧版向日葵 2.2 首先打开nmap扫描向日葵主机端口 2.3 在浏览器中访问ip端口号cgi-bin/rpc?actionverify-haras &#xff08;端口号&#xff1a;每一个都尝试&#xff0c;直到获取到session值…...

Postman中的负载均衡测试:确保API的高可用性

Postman中的负载均衡测试&#xff1a;确保API的高可用性 在微服务架构和分布式系统中&#xff0c;API的负载均衡是确保系统高可用性和可扩展性的关键技术之一。Postman作为一个多功能的API开发和测试平台&#xff0c;提供了多种工具来帮助测试人员模拟高负载情况下的API表现。…...

anaconda+tensorflow+keras+jupyter notebook搭建过程(CPU版)

AnacondaTensorFlowKeras 环境搭建教程...

LitCTF2024赛后web复现

复现要求&#xff1a;看wp做一遍&#xff0c;自己做一遍&#xff0c;第二天再做一遍。&#xff08;一眼看出来就跳过&#xff09; 目录 [LitCTF 2024]浏览器也能套娃&#xff1f; [LitCTF 2024]一个....池子&#xff1f; [LitCTF 2024]高亮主题(划掉)背景查看器 [LitCTF 2…...

Elasticsearch:跨集群使用 ES|QL

警告&#xff1a;ES|QL 的跨集群搜索目前处于技术预览阶段&#xff0c;可能会在未来版本中更改或删除。Elastic 将努力解决任何问题&#xff0c;但技术预览中的功能不受官方 GA 功能的支持 SLA 约束。 使用 ES|QL&#xff0c;你可以跨多个集群执行单个查询。 前提&#xff1a; …...

学习笔记4:docker和k8s选择简述

docker和 k8s 占用资源 使用客户体量Docker 和 Kubernetes&#xff08;K8s&#xff09;都是流行的容器化技术&#xff0c;但它们在资源管理和使用上有一些不同。以下是关于两者资源占用和使用客户体量的详细比较&#xff0c;基于具体数据和信息&#xff1a; Docker 资源占用…...

关于锁策略

在Java中对于多线程来说&#xff0c;锁是一种重要且必不可少的东西&#xff0c;那么我们将如何使用以及在什么时候使用什么样的锁呢&#xff1f;请各位往下看 悲观锁VS乐观锁 悲观锁&#xff1a; 在多线程环境中&#xff0c;冲突是非常常见的&#xff0c;所以在执行操作之前…...

昇思25天学习打卡营第3天|基础知识-数据集Dataset

目录 环境 环境 导包 数据集加载 数据集迭代 数据集常用操作 shuffle map batch 自定义数据集 可随机访问数据集 可迭代数据集 生成器 MindSpore提供基于Pipeline的数据引擎&#xff0c;通过数据集&#xff08;Dataset&#xff09;和数据变换&#xff08;Transfor…...

C++11新特性——智能指针——参考bibi《 原子之音》的视频以及ChatGpt

智能指针 一、内存泄露1.1 内存泄露常见原因1.2 如何避免内存泄露 二、实例Demo2.1 文件结构2.2 Dog.h2.3 Dog.cpp2.3 mian.cpp 三、独占式智能指针:unique _ptr3.1 创建方式3.1.1 ⭐从原始(裸)指针转换&#xff1a;3.1.2 ⭐⭐使用 new 关键字直接创建&#xff1a;3.1.3 ⭐⭐⭐…...

“微软蓝屏”全球宕机,敲响基础软件自主可控警钟

上周五&#xff0c;“微软蓝屏”“感谢微软 喜提假期”等词条冲上热搜&#xff0c;全球百万打工人受此影响&#xff0c;共同见证这一历史性事件。据微软方面发布消息称&#xff0c;旗下Microsoft 365系列服务出现访问中断。随后在全球范围内&#xff0c;包括企业、政府、个人在…...

【Linux C | 网络编程】进程间传递文件描述符socketpair、sendmsg、recvmsg详解

我们的目的是&#xff0c;实现进程间传递文件描述符&#xff0c;是指 A进程打开文件fileA,获得文件描述符为fdA&#xff0c;现在 A进程要通过某种方法&#xff0c;传递fdA&#xff0c;使得另一个进程B&#xff0c;获得一个新的文件描述符fdB&#xff0c;这个fdB在进程B中的作用…...

高并发内存池(六)Page Cache回收功能的实现

当Page Cache接收了一个来自Central Cache的Span&#xff0c;根据Span的起始页的_pageId来对前一页所对应的Span进行查找&#xff0c;并判断该Span&#xff0c;是否处于使用状态&#xff0c;从而看是否可以合并&#xff0c;如果可以合并继续向前寻找。 当该Span前的空闲Span查…...

Leetcode 3576. Transform Array to All Equal Elements

Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接&#xff1a;3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到&#xf…...

【JavaEE】-- HTTP

1. HTTP是什么&#xff1f; HTTP&#xff08;全称为"超文本传输协议"&#xff09;是一种应用非常广泛的应用层协议&#xff0c;HTTP是基于TCP协议的一种应用层协议。 应用层协议&#xff1a;是计算机网络协议栈中最高层的协议&#xff0c;它定义了运行在不同主机上…...

【第二十一章 SDIO接口(SDIO)】

第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...

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

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

【Java_EE】Spring MVC

目录 Spring Web MVC ​编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 ​编辑参数重命名 RequestParam ​编辑​编辑传递集合 RequestParam 传递JSON数据 ​编辑RequestBody ​…...

DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”

目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...

【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)

本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...

实战设计模式之模板方法模式

概述 模板方法模式定义了一个操作中的算法骨架&#xff0c;并将某些步骤延迟到子类中实现。模板方法使得子类可以在不改变算法结构的前提下&#xff0c;重新定义算法中的某些步骤。简单来说&#xff0c;就是在一个方法中定义了要执行的步骤顺序或算法框架&#xff0c;但允许子类…...

数据结构第5章:树和二叉树完全指南(自整理详细图文笔记)

名人说&#xff1a;莫道桑榆晚&#xff0c;为霞尚满天。——刘禹锡&#xff08;刘梦得&#xff0c;诗豪&#xff09; 原创笔记&#xff1a;Code_流苏(CSDN)&#xff08;一个喜欢古诗词和编程的Coder&#x1f60a;&#xff09; 上一篇&#xff1a;《数据结构第4章 数组和广义表》…...

车载诊断架构 --- ZEVonUDS(J1979-3)简介第一篇

我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 做到欲望极简,了解自己的真实欲望,不受外在潮流的影响,不盲从,不跟风。把自己的精力全部用在自己。一是去掉多余,凡事找规律,基础是诚信;二是…...