《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底层:堆>
前言 大家好,我目前在学习java。之前也学了一段时间,但是没有发布博客。时间过的真的很快。我会利用好这个暑假,来复习之前学过的内容,并整理好之前写过的博客进行发布。如果博客中有错误或者没有读懂的地方。热烈欢迎大家在评论区…...
Matrix Equation(高斯线性异或消元+bitset优化)
题目: 登录—专业IT笔试面试备考平台_牛客网 思路: 我们发现对于矩阵C可以一列一列求。 mod2,当这一行相乘1的个数为奇数时,z(i,j)为1,偶数为0,是异或消元。 对于b[i,j]*c[i,j],b[i,j]可以…...

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

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

【论文精读】 | 基于图表示的视频抑郁症识别的两阶段时间建模框架
文章目录 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音频文件
需求 开始录音——监听录音数据——结束录音 在监听录音数据过程中:客户端每100ms给前端传输一次数据(pcm数据转成base64),前端需要将base64片段解码、合并、添加WAV头、转成File、上传到 OSS之后将 url 给到服务端处理。 {num…...

eclipse ui bug
eclipse ui bug界面缺陷,可能项目过多,特别maven项目过多,下载,自动编译,加载更新界面异常 所有窗口死活Restore不回去了 1)尝试创建项目,还原界面,失败 2)关闭所有窗口&…...
前端获取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 (端口号:每一个都尝试,直到获取到session值…...
Postman中的负载均衡测试:确保API的高可用性
Postman中的负载均衡测试:确保API的高可用性 在微服务架构和分布式系统中,API的负载均衡是确保系统高可用性和可扩展性的关键技术之一。Postman作为一个多功能的API开发和测试平台,提供了多种工具来帮助测试人员模拟高负载情况下的API表现。…...

anaconda+tensorflow+keras+jupyter notebook搭建过程(CPU版)
AnacondaTensorFlowKeras 环境搭建教程...

LitCTF2024赛后web复现
复现要求:看wp做一遍,自己做一遍,第二天再做一遍。(一眼看出来就跳过) 目录 [LitCTF 2024]浏览器也能套娃? [LitCTF 2024]一个....池子? [LitCTF 2024]高亮主题(划掉)背景查看器 [LitCTF 2…...

Elasticsearch:跨集群使用 ES|QL
警告:ES|QL 的跨集群搜索目前处于技术预览阶段,可能会在未来版本中更改或删除。Elastic 将努力解决任何问题,但技术预览中的功能不受官方 GA 功能的支持 SLA 约束。 使用 ES|QL,你可以跨多个集群执行单个查询。 前提: …...
学习笔记4:docker和k8s选择简述
docker和 k8s 占用资源 使用客户体量Docker 和 Kubernetes(K8s)都是流行的容器化技术,但它们在资源管理和使用上有一些不同。以下是关于两者资源占用和使用客户体量的详细比较,基于具体数据和信息: Docker 资源占用…...
关于锁策略
在Java中对于多线程来说,锁是一种重要且必不可少的东西,那么我们将如何使用以及在什么时候使用什么样的锁呢?请各位往下看 悲观锁VS乐观锁 悲观锁: 在多线程环境中,冲突是非常常见的,所以在执行操作之前…...

昇思25天学习打卡营第3天|基础知识-数据集Dataset
目录 环境 环境 导包 数据集加载 数据集迭代 数据集常用操作 shuffle map batch 自定义数据集 可随机访问数据集 可迭代数据集 生成器 MindSpore提供基于Pipeline的数据引擎,通过数据集(Dataset)和数据变换(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 ⭐从原始(裸)指针转换:3.1.2 ⭐⭐使用 new 关键字直接创建:3.1.3 ⭐⭐⭐…...

“微软蓝屏”全球宕机,敲响基础软件自主可控警钟
上周五,“微软蓝屏”“感谢微软 喜提假期”等词条冲上热搜,全球百万打工人受此影响,共同见证这一历史性事件。据微软方面发布消息称,旗下Microsoft 365系列服务出现访问中断。随后在全球范围内,包括企业、政府、个人在…...
【Linux C | 网络编程】进程间传递文件描述符socketpair、sendmsg、recvmsg详解
我们的目的是,实现进程间传递文件描述符,是指 A进程打开文件fileA,获得文件描述符为fdA,现在 A进程要通过某种方法,传递fdA,使得另一个进程B,获得一个新的文件描述符fdB,这个fdB在进程B中的作用…...
高并发内存池(六)Page Cache回收功能的实现
当Page Cache接收了一个来自Central Cache的Span,根据Span的起始页的_pageId来对前一页所对应的Span进行查找,并判断该Span,是否处于使用状态,从而看是否可以合并,如果可以合并继续向前寻找。 当该Span前的空闲Span查…...
RestClient
什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端,它允许HTTP与Elasticsearch 集群通信,而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级ÿ…...

手游刚开服就被攻击怎么办?如何防御DDoS?
开服初期是手游最脆弱的阶段,极易成为DDoS攻击的目标。一旦遭遇攻击,可能导致服务器瘫痪、玩家流失,甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案,帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...

深入剖析AI大模型:大模型时代的 Prompt 工程全解析
今天聊的内容,我认为是AI开发里面非常重要的内容。它在AI开发里无处不在,当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗",或者让翻译模型 "将这段合同翻译成商务日语" 时,输入的这句话就是 Prompt。…...

【入坑系列】TiDB 强制索引在不同库下不生效问题
文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...

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

STM32F4基本定时器使用和原理详解
STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...

Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具
文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...
2023赣州旅游投资集团
单选题 1.“不登高山,不知天之高也;不临深溪,不知地之厚也。”这句话说明_____。 A、人的意识具有创造性 B、人的认识是独立于实践之外的 C、实践在认识过程中具有决定作用 D、人的一切知识都是从直接经验中获得的 参考答案: C 本题解…...
Angular微前端架构:Module Federation + ngx-build-plus (Webpack)
以下是一个完整的 Angular 微前端示例,其中使用的是 Module Federation 和 npx-build-plus 实现了主应用(Shell)与子应用(Remote)的集成。 🛠️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...
智能AI电话机器人系统的识别能力现状与发展水平
一、引言 随着人工智能技术的飞速发展,AI电话机器人系统已经从简单的自动应答工具演变为具备复杂交互能力的智能助手。这类系统结合了语音识别、自然语言处理、情感计算和机器学习等多项前沿技术,在客户服务、营销推广、信息查询等领域发挥着越来越重要…...