Java -数据结构,【优先级队列 / 堆】
一、二叉树的顺序存储
在前面我们已经讲了二叉树的链式存储,就是一棵树的左孩子和右孩子
而现在讲的是:顺序存储一棵二叉树。
1.1、存储方式
使用数组保存二叉树结构,方式即将二叉树用层序遍历方式放入数组中。 一般只适合表示完全二叉树,因为非完全二叉树会有空间的浪费。
这种方式的主要用法就是堆的表示
下标关系
已知双亲(parent)的下标,则:
左孩子(left)下标 = 2 * parent + 1;
右孩子(right)下标 = 2 * parent + 2;
已知孩子(不区分左右)(child)下标,则:
双亲(parent)下标 = (child - 1) / 2;
也就是前面我们将的性质5:
对于具有n个结点的完全二叉树,如果按照从上至下从左至右的顺序对所有节点从0开始编号,则对于序号为i的结点有:
(1)若i>0,双亲序号:(i-1)/2;i=0,i为根结点编号,无双亲结点
(2)若2i+1<n,左孩子序号:2i+1,否则无左孩子
(3)若2i+2<n,右孩子序号:2i+2,否则无右孩子
二、堆
2.1、概念
- 堆逻辑上是一棵完全二叉树
- 堆物理上是保存在数组中
- 满足任意结点的值都大于其子树中结点的值,叫做大堆,或者大根堆,或者最大堆
- 反之,则是小堆,或者小根堆,或者最小堆
- 堆的基本作用是,快速找集合中的最值 :无论是 大根堆还是小根堆, 它们的 最值【最大值 和 最小值】都处于 二叉树的 根结点处。要想获得 最值,直接 peek 方法,就能获得 树 的 根结点值 / 最值。
2.2、操作-向下调整
前提:左右子树必须已经是一个 堆 / 逻辑上是一棵完全二叉树。
将一组 记录完全二叉树数据 的 数组 转换成 大根堆。
向下调整出现的问题:
得出结论:其实每棵树的调整结束位置都是一样的︰不能超过数组长度。
如何构造一个 向下调整的函数 - 重点
public class TestHeap {public int[] elem;//底层是一个数组public int usedSize;//public TestHeap(){this.elem = new int[10];}/*** 创建堆* @param array 堆里面存放的元素*/public void creatHeap(int[] array){//将array数组的元素存入elme 数组for (int i = 0; i < array.length; i++) {elem[i] = array[i] ;usedSize++;}for (int praent = (usedSize-1-1)/2; praent >= 0; praent--) {shiftDown(praent,usedSize);}}/*** 向下调整* @param praent 每棵子树的父亲节点* @param len 调整的结束位置,不能大于数组的长度*/public void shiftDown(int praent, int len){int child = 2+praent +1;while (child < len){if(child + 1 > len && this.elem[child] < this.elem[child+1]){child++;}if(elem[child] > elem[praent]){int tmp = elem[child];elem[child] = elem[praent];elem[praent] = tmp;}else {break;}}}
}
测试一下:
模拟实现 堆 的 时间复杂度
上图转载于:堆 / 优先队列
粗略估算,可以认为是在循环中执行向下调整,为 O(n * log(n))
(了解)实际上是 O(n)
堆排序中建堆过程时间复杂度O(n)怎么来的?
2.3、操作-建堆
下面我们给出一个数组,这个数组逻辑上可以看做一颗完全二叉树,但是还不是一个堆,现在我们通过算法,把它构建成一个堆。根节点左右子树不是堆,我们怎么调整呢?这里我们从倒数的第一个非叶子节点的子树开始调整,一直调整到根节点的树,就可以调整成堆
图示(以大堆为例):
// 建堆前
int[] array = { 1,5,3,8,7,6 };
// 建堆后
int[] array = { 8,7,6,5,1,3 };
三、堆的应用-优先级队列
3.1、概念
在很多应用中,我们通常需要按照优先级情况对待处理对象进行处理,比如首先处理优先级最高的对象,然后处理次
高的对象。最简单的一个例子就是,在手机上玩游戏的时候,如果有来电,那么系统应该优先处理打进来的电话。
在这种情况下,我们的数据结构应该提供两个最基本的操作,一个是返回最高优先级对象,一个是添加新的对象。这
种数据结构就是优先级队列(Priority Queue)
优先级队列的实现方式有很多,但最常见的是使用堆来构建
3.2、堆的基本操作
我们知道堆分为大根堆和小根堆,那Java中自带的默认是大根堆还是小根堆???
Java集合中默认是小根堆
我们测试一下:
public static void main(String[] args) {PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();priorityQueue.offer(12);priorityQueue.offer(3);priorityQueue.offer(18);System.out.println(priorityQueue.poll());System.out.println(priorityQueue.poll());}
优先级队列 - 模拟实现入队 – offer()
/*** 插入元素* @param val*/public void offer(int val){if(isFull()){//扩容elem = Arrays.copyOf(elem,2*elem.length);}//没有满就将val放在数组的最后一个元素elem[usedSize] = val;usedSize++;//然后就调整堆,使其成为一个大根堆shiftUp(usedSize-1,val);}/**** @param child 孩子节点的坐标* @param val 要插入的值*/public void shiftUp(int child, int val){int praent = (child - 1) / 2;while(praent > 0){if(elem[child] > elem[praent]){int tmp = elem[child];elem[child] = elem[praent];elem[praent] = tmp;//然后再改变child 和 praent 的指向child = praent;praent = (child - 1) / 2;}else {break;}}}public boolean isFull(){return this.elem.length == usedSize;}
优先级队列 - 模拟实现出队 – poll()
public int poll(){if(isFull()){throw new RuntimeException("队列为null!");}//先将0下标和数组的最后一个元素交换int tmp = elem[0];elem[0] = elem[usedSize-1];elem[usedSize-1] = tmp;usedSize--;//然后向下调整0下标这棵树shiftDown(0,usedSize);return tmp;}//判断是否为nullpublic boolean isEmpty(){if (usedSize == 0){return true;}return false;}
总程序
public class Heap {public int[] elements;// 底层数组public int usedSize;// 有效元素个数// 构造方法public Heap(){// 数组初始化容量this.elements = new int[10];}// 创建堆,获取 输入数组 的 数据public void creationHeap(int[] array){this.usedSize += array.length;if(isFull()){this.elements = Arrays.copyOf(this.elements,this.elements.length*2);}this.elements = Arrays.copyOf(array,array.length);for(int parent = (this.usedSize -1 - 1)/2 ;parent >= 0;parent--){// 向下调整shiftDown(parent,this.usedSize);}}// 向下调整public void shiftDown(int parent,int len){int child = parent * 2 + 1;// 左孩子// 能进入该循环,说明 这个 parent 只少有一个孩子。while(child < len){// 获取 左右孩子的最大值if(child+1 < len &&this.elements[child] < this.elements[child+1]){child++;}// 判断 孩子最大值 是否 比 双亲节点 val 值 大// 如果大,就需要进行交换if(this.elements[child] > this.elements[parent]){int tmp = elements[child];elements[child] = elements[parent];elements[parent] = tmp;// 见附图parent = child;child = parent * 2 + 1;}else{break;}}}// 入队操作public void offer(int val){if(isFull()){// 扩容this.elements = Arrays.copyOf(this.elements,this.elements.length * 2);}elements[usedSize++] = val;//usedSize++;shiftUp(usedSize-1);// 有效元素个数 是 usedSize,最后一个元素的下标是 usedSize -1}private void shiftUp(int child){int parent = (child - 1)/2;while(child > 0){if(this.elements[child] > this.elements[parent]){int tmp = this.elements[child];this.elements[child] = this.elements[parent];this.elements[parent] = tmp;child = parent;parent = (child - 1) / 2;}else{break;}}}// 判断队列满没满public boolean isFull(){return this.usedSize >= this.elements.length;}// 出队操作public int poll(){if(isEmpty()){throw new RuntimeException("优先级队列为空!");}int tmp = this.elements[0];this.elements[0] = this.elements[this.usedSize -1];this.elements[this.usedSize - 1] = tmp;this.usedSize--;shiftDown(0,usedSize);return tmp;}// 判断队列 空不空public boolean isEmpty(){return this.usedSize == 0;}public int peek(){if(isEmpty()){throw new RuntimeException("优先级队列为空!");}return this.elements[0];}}
四、校招 – TopK问题
问题描述:
从arr[1, n]这n个数中,找出最大的k个数,这就是经典的TopK问题。(从100万中找出最大的k个数)
栗子:
从arr[1, 12]={5,3,7,1,8,2,9,4,7,2,6,6} 这n=12个数中,找出最大的k=5个。
总结
1、如果求前K个最大的元素,要建一个小根堆。
2、如果求 前K个最小的元素,要建一个大根堆。
3、如果是求第k大的元素,建一个小堆,小根堆 堆顶的元素就是第k大的元素。
4、如果是求第k小的元素,建一个大堆,大根堆 堆顶的元素就是第k小的元素。
五、堆的其他应用-堆排序
1、将数据调整为 大根堆、
2、0 下标 与 最后一个未排序的元素进行交换即可。
3、循环上述两个操作,直至 最后一个未排序的元素 下标为 0.。
/*** 堆排序*/public void heapSort(){int last = usedSize - 1;while (last > 0){int tmp = elem[0];elem[0] = elem[last ];elem[last ] = tmp;shiftDown1(0,last);last --;}}/***向下调整* @param parent* @param len*/public void shiftDown1(int parent,int len){int child = parent * 2 + 1;// 左孩子// 能进入该循环,说明 这个 parent 只少有一个孩子。while(child < len){// 获取 左右孩子的最大值if(child+1 < len &&this.elem[child] < this.elem[child+1]){child++;}// 判断 孩子最大值 是否 比 双亲节点 val 值 大// 如果大,就需要进行交换if(this.elem[child] > this.elem[parent]){int tmp = elem[child];elem[child] = elem[parent];elem[parent] = tmp;parent = child;child = parent * 2 + 1;}else{break;}}}
相关文章:

Java -数据结构,【优先级队列 / 堆】
一、二叉树的顺序存储 在前面我们已经讲了二叉树的链式存储,就是一棵树的左孩子和右孩子 而现在讲的是:顺序存储一棵二叉树。 1.1、存储方式 使用数组保存二叉树结构,方式即将二叉树用层序遍历方式放入数组中。 一般只适合表示完全二叉树&a…...

Python+Qt指纹录入识别考勤系统
PythonQt指纹录入识别考勤系统如需安装运行环境或远程调试,见文章底部个人QQ名片,由专业技术人员远程协助!前言这篇博客针对<<PythonQt指纹录入识别考勤系统>>编写代码,代码整洁,规则,易读。 学…...

K_A14_004 基于STM32等单片机驱动旋转角度传感器模块 串口与OLED0.96双显示
K_A14_004 基于STM32等单片机驱动旋转角度传感器模块 串口与OLED0.96双显示一、资源说明二、基本参数参数引脚说明三、驱动说明IIC地址/采集通道选择/时序对应程序:四、部分代码说明1、接线引脚定义1.1、STC89C52RC旋转角度传感器模块1.2、STM32F103C8T6旋转角度传感器模块五、…...
2023年全国最新机动车签字授权人精选真题及答案12
百分百题库提供机动车签字授权人考试试题、机动车签字授权人考试预测题、机动车签字授权人考试真题、机动车签字授权人证考试题库等,提供在线做题刷题,在线模拟考试,助你考试轻松过关。 11.注册登记前所有机动车都应进行安全技术检验。 答案…...
Linux小黑板(10):信号
我们写在linux系统环境下写一个程序,唔,"它的功能是每隔1s向屏幕打印hello world。"这时,我们在键盘上按出"Ctrl C"后,进程会发生什么??我们清晰地看到,进程已经在我们按出"Ctrl…...

GO 语言基础语法一 (快速入门 Go 语言)
Go语言基础语法一. golang 标识符,关键字,命名规则二. golang 变量三. golang 常量四. golang 数据类型五. golang 布尔类型六. golang 数字类型七. golang 字符串1. go语言字符串字面量2. go语言字符串连接(1). 使用加号(2). 使用 fmt.Sprintf() 函数(3…...

Java高效率复习-SpringMVC[SpringMVC-2]
SpringMVC获取请求参数 SpringMVC获取请求参数的两种方式↓ 通过ServletAPI获取请求参数 将HttpServletRequest作为控制器方法的形参,此时HttpServletRequest类型的参数表示封装了当前请求的请求报文的对象 通过request的API——getParameter(String s)方法来获取…...

【前端】一个更底层库-React基础知识点
目录Reat是什么?为什么要使用React类库比较容易学习,API非常少。组件内聚,容易组合原生组件和自定义组件融合渲染状态/属性驱动全局更新commonjs生态圈/工具栏完善React基础知识JSX概述JSX嵌入变量Event事件组合组合CHILDREN总结大家好&#…...
C++ 之枚举类型
文章目录参考描述枚举类型枚举类型枚举变量的声明及定义细节枚举常量的默认初始值枚举常量不可被修改赋值运算枚举常量与数据类型为枚举常量指定数据类型可选择的数据类型特殊的 Bool强枚举类型命名冲突强枚举类型参考 项目描述菜鸟教程C 枚举类型详解精通C (第九版…...

软件测试用例(3)
按照测试对象划分: 一)界面测试: 1)软件只是一种工具,软件和人的信息交流是通过界面来进行的,界面是软件和用户交流的最直接的一层,界面的设计决定了用户对于我们设计软件的第一映像,界面如同人的面孔,具有最吸引用户的…...

Spring——Bean管理-注解方式进行属性注入
Spring针对Bean管理中创建对象提供的注解有哪些?Component:普通Service:业务逻辑层Controller:controller层Repository:dao层用注解的方式是为什么?简化xml方式开发,只需要注解就可以完成在配置…...
【设计模式之美 设计原则与思想:设计原则】20 | 理论六:我为何说KISS、YAGNI原则看似简单,却经常被用错?
上几节课中,我们学习了经典的 SOLID 原则。今天,我们讲两个设计原则:KISS 原则和 YAGNI 原则。其中,KISS 原则比较经典,耳熟能详,但 YAGNI 你可能没怎么听过,不过它理解起来也不难。 理解这两个…...
Java代码弱点与修复之——Copy-paste error(复制粘贴错误)
弱点描述 Copy-paste error,复制粘贴错误。 是指在复制和粘贴代码时产生的错误。这种错误通常是由于程序员在复制代码时未正确编辑所复制的代码或编辑复制后的代码时忘记更改一些值或参数而导致的。复制粘贴错误可能会导致程序逻辑错误、编译错误或运行时错误。 示例代码 …...

Editor.md 的使用方法及图片处理
目录1. 资源下载2. 生成页面2.1 编辑和预览页面2.2 文本渲染页面3. 图片上传3.1 前端配置3.2 后端接口4. 图片粘贴[^2]1. 资源下载 官网下载 gitee 下载 2. 生成页面 2.1 编辑和预览页面 将资源(精简后 Editor.md 资源1)导入项目: 按照官…...
剑指 Offer II 018. 有效的回文
题目链接 剑指 Offer II 018. 有效的回文 easy 题目描述 给定一个字符串 s,验证 s是否是 回文串 ,只考虑字母和数字字符,可以忽略字母的大小写。 本题中,将空字符串定义为有效的 回文串 。 示例 1: 输入: s “A man, a plan, …...
Elasticsearch分析器(Analyzer)
Elasticsearch分析器(Analyzer) 文章目录Elasticsearch分析器(Analyzer)分析器概念内置分析器(8.6版本)自定义分析器elasticsearch-analysis-ik(简称ik,💕14.8kÿ…...
P6入门:了解P6 Professional 工具栏及地图分享
目录 引言 相关分享 引言 凭借更大的灵活性和增强的自定义功能,最新版本的 Oracle Primavera P6 Professional 的界面比早期版本有了巨大改进。对于有经验的伙伴来说,它仍然是熟悉的领域,几乎所有预期的功能都显示在前面。该界面可以更好地…...

习题30 if elif else 语句
people 30#变量people赋值30 cars 40#变量cars赋值40 buses 15#变量buses赋值 if cars > people:#如果出租车比人多print("We should take the cars")#我们坐出租车 elif cars < people:#elif后面必须跟条件,print("We should not take the…...

32 openEuler使用LVM管理硬盘-管理卷组
文章目录32 openEuler使用LVM管理硬盘-管理卷组32.1 创建卷组32.2 查看卷组32.3 修改卷组属性32.4 扩展卷组32.5 收缩卷组32.6 删除卷组32 openEuler使用LVM管理硬盘-管理卷组 32.1 创建卷组 可在root权限下通过vgcreate命令创建卷组。 vgcreate [option] vgname pvname ...…...

Jackson CVE-2017-17485 反序列化漏洞
0x00 前言 同CVE-2017-15095一样,是CVE-2017-7525黑名单绕过的漏洞,主要还是看一下绕过的调用链利用方式。 可以先看: Jackson 反序列化漏洞原理 或者直接看总结也可以: Jackson总结 涉及版本:2.8.10和2.9.x至2.…...
React Native 开发环境搭建(全平台详解)
React Native 开发环境搭建(全平台详解) 在开始使用 React Native 开发移动应用之前,正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南,涵盖 macOS 和 Windows 平台的配置步骤,如何在 Android 和 iOS…...

LeetCode - 394. 字符串解码
题目 394. 字符串解码 - 力扣(LeetCode) 思路 使用两个栈:一个存储重复次数,一个存储字符串 遍历输入字符串: 数字处理:遇到数字时,累积计算重复次数左括号处理:保存当前状态&a…...
pam_env.so模块配置解析
在PAM(Pluggable Authentication Modules)配置中, /etc/pam.d/su 文件相关配置含义如下: 配置解析 auth required pam_env.so1. 字段分解 字段值说明模块类型auth认证类模块,负责验证用户身份&am…...
渲染学进阶内容——模型
最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...

【项目实战】通过多模态+LangGraph实现PPT生成助手
PPT自动生成系统 基于LangGraph的PPT自动生成系统,可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析:自动解析Markdown文档结构PPT模板分析:分析PPT模板的布局和风格智能布局决策:匹配内容与合适的PPT布局自动…...
土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等
🔍 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术,可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势,还能有效评价重大生态工程…...
Python如何给视频添加音频和字幕
在Python中,给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加,包括必要的代码示例和详细解释。 环境准备 在开始之前,需要安装以下Python库:…...

AI书签管理工具开发全记录(十九):嵌入资源处理
1.前言 📝 在上一篇文章中,我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源,方便后续将资源打包到一个可执行文件中。 2.embed介绍 🎯 Go 1.16 引入了革命性的 embed 包,彻底改变了静态资源管理的…...

Springboot社区养老保险系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,社区养老保险系统小程序被用户普遍使用,为方…...

SAP学习笔记 - 开发26 - 前端Fiori开发 OData V2 和 V4 的差异 (Deepseek整理)
上一章用到了V2 的概念,其实 Fiori当中还有 V4,咱们这一章来总结一下 V2 和 V4。 SAP学习笔记 - 开发25 - 前端Fiori开发 Remote OData Service(使用远端Odata服务),代理中间件(ui5-middleware-simpleproxy)-CSDN博客…...