Java中的Heap(堆)(如果想知道Java中有关堆的知识点,那么只看这一篇就足够了!)

news/2024/9/18 12:05:32/ 标签: java, 开发语言, 学习, 数据结构, intellij idea

        前言:(Heap)是一种特殊的完全二叉树,它在诸多算法中有着广泛的应用,本文将详细介绍Java中的堆。


✨✨✨这里是秋刀鱼不做梦的BLOG

✨✨✨想要了解更多内容可以访问我的主页秋刀鱼不做梦-CSDN博客

先让我们看一下本文大致的讲解内容:

目录

1.堆的初识

        堆的定义

2.堆的存储方式 + 基本结论

        (1)堆的存储方式

        (2)堆中的基本结论

3.堆的创建

        (1)逐个插入元素

        (2)批量建堆

4.堆的基本操作

(1)插入操作

(2)删除操作

(3)返回堆顶元素

(4)判断堆是否为空


1.堆的初识

        ——堆是一种特殊的完全二叉树,分为最大堆(大顶堆)和最小堆(小顶堆)。最大堆的每个节点的值都大于或等于其子节点的值,最小堆的每个节点的值都小于或等于其子节点的值。

        堆常用于实现优先队列(PriorityQueue),在图算法(如Dijkstra最短路径算法和Prim最小生成树算法)中也有重要应用。(读者若有兴趣可以自行了解!

        堆的定义

        ——堆是一种特殊的完全二叉树,满足以下两个条件:

  1. 完全二叉树:

    1. 除了最后一层,其他层的节点都是满的,并且最后一层的节点从左到右连续排列。(如图)

  1. 堆性质:

    • 最大堆:每个节点的值都大于或等于其子节点的值。

    • 最小堆:每个节点的值都小于或等于其子节点的值。

        堆的这些性质使得堆顶元素(根节点)在最大堆中是最大值,在最小堆中是最小值。这样我们就大致的了解了什么是堆了!

2.堆的存储方式 + 基本结论

        (1)堆的存储方式

        从堆的概念可知,堆是一棵完全二叉树,通常情况下,堆是通过数组来实现,因为数组可以高效地访问任意位置的元素,并且通过简单的算术操作可以找到父节点和子节点的位置。(如左图a)

        但是对于二叉树中非完全二叉树,则不适合使用顺序方式进行存储,因为为了能够还原二叉树,空间中必须要存储空节点,就会导致空间利用率比较低(如右图b)

        ——这样我们就知道了堆就是将链式结构的完全二叉树转换为数组形式进行存储。

        (2)堆中的基本结论

        那么了解完了堆的基本存储形式,接下来让我们看看堆中的基本结论,从上文中我们已经提及在堆中我们可以通过简单的算术操作可以找到父节点和子节点的位置,那么如何实现呢?

现在我们假设 i 为节点在数组中的下标,则有:

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

       

        ——读者可以根据上图进行自我验证!!!

这样我们就大致的了解了堆中的基本结论了。

3.堆的创建

        ——创建堆的过程可以通过两种方式实现:逐个插入元素(使用向上调整算法)批量建堆(使用向下调整算法)。逐个插入元素的方法相对简单,但批量建堆的方法效率更高。

        (1)逐个插入元素

        这种方法通过逐个插入元素来创建堆,每次插入新元素后,使用向上调整算法操作将其移动到正确位置,以保持堆的性质。

java">import java.util.Arrays;public class MaxHeap {private int[] elem; // 存储堆元素的数组private int usedSize; // 堆中元素的数量// 构造函数,初始化堆的容量public MaxHeap(int maxSize) {this.elem = new int[maxSize];this.usedSize = 0;}// 逐个插入元素的方法public void offer(int val) {// 如果堆已满,扩展数组容量为原来的两倍if (isFull()) {elem = Arrays.copyOf(elem, 2 * elem.length);}// 将新元素放入数组的最后一位elem[usedSize++] = val;// 进行上浮操作,保持堆的性质shiftUp(usedSize - 1);}// 检查堆是否已满private boolean isFull() {return usedSize == elem.length;}// 上浮操作,将新插入的元素移动到正确位置private void shiftUp(int child) {int parent = (child - 1) / 2;// 当child不为根节点,并且父节点的值小于子节点的值时,进行交换while (parent >= 0) {if (elem[parent] < elem[child]) {swap(parent, child);child = parent;parent = (child - 1) / 2;} else {break;}}}// 交换数组中的两个元素private void swap(int fpos, int spos) {int tmp = elem[fpos];elem[fpos] = elem[spos];elem[spos] = tmp;}// 主函数测试public static void main(String[] args) {MaxHeap maxHeap = new MaxHeap(10);maxHeap.offer(3);maxHeap.offer(1);maxHeap.offer(6);maxHeap.offer(5);maxHeap.offer(2);maxHeap.offer(4);System.out.println("Heap array: " + Arrays.toString(maxHeap.elem));}
}

        其核心逻辑就是将一个一个数据插入到数组的最后,然后根据堆(最大堆 或 最小堆)的基本概念来创建一个堆。

        ——如上图插入一个22数据,然后根据向上调整算法来实现创建最大堆。

        (2)批量建堆

        批量建堆的方法首先将所有元素放入数组中,然后从最后一个非叶子节点开始进行向下调整算法的操作,将其调整到正确位置。

java">import java.util.Arrays;public class MaxHeap {private int[] elem; // 存储堆元素的数组private int usedSize; // 堆中元素的数量// 构造函数,初始化堆的容量public MaxHeap(int maxSize) {this.elem = new int[maxSize];this.usedSize = 0;}// 批量建堆的方法public void createHeap(int[] array) {// 将数组的每个元素插入到堆中for (int i = 0; i < array.length; i++) {elem[i] = array[i];usedSize++;}// 从最后一个非叶节点开始进行向下调整算法// 计算最后一个非叶节点的索引for (int parent = (usedSize - 1 - 1) / 2; parent >= 0; parent--) {shiftDown(parent, usedSize);}}// 下沉操作,将根节点向下移动以维持堆的性质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(child, root);root = child; // 更新根节点的索引child = 2 * root + 1; // 计算新的左孩子索引} else {break; // 如果孩子节点不大于根节点,结束向下调整}}}// 交换数组中两个元素的位置private void swap(int pos1, int pos2) {int temp = elem[pos1]; // 临时保存第一个位置的元素elem[pos1] = elem[pos2]; // 将第二个位置的元素赋值到第一个位置elem[pos2] = temp; // 将临时保存的元素赋值到第二个位置}// 主函数用于测试public static void main(String[] args) {MaxHeap maxHeap = new MaxHeap(10);int[] array = {3, 1, 6, 5, 2, 4};maxHeap.createHeap(array);System.out.println("Heap array: " + Arrays.toString(maxHeap.elem));}
}

        其核心思路就是先将数据全部放入数组中,在从下往上的一个一个的建立 (最大堆 或 最小堆),直到整棵树变为 (最大堆 或 最小堆)

        这样我们就了解了堆的两种创建方式了!

4.堆的基本操作

        堆的基本操作包括插入、删除和取出堆定元素、判断堆是否为空等。现在让我们详细介绍这些操作的实现方法。

(1)插入操作

        插入操作其实就是我们在创建堆中的逐个插入元素的操作,这里再让我们回顾一下:

java">// 插入元素的方法public void offer(int val) {// 如果堆已满,扩展数组容量为原来的两倍if (isFull()) {elem = Arrays.copyOf(elem, 2 * elem.length);}// 将新元素放入数组的最后一位elem[usedSize++] = val;// 进行上浮操作,保持堆的性质shiftUp(usedSize - 1);}// 检查堆是否已满private boolean isFull() {return usedSize == elem.length;}// 向上调整算法,将新插入的元素移动到正确位置private void shiftUp(int child) {int parent = (child - 1) / 2;// 当child不为根节点,并且父节点的值小于子节点的值时,进行交换while (parent >= 0) {if (elem[parent] < elem[child]) {swap(parent, child);child = parent;parent = (child - 1) / 2;} else {break;}}}

(2)删除操作

        删除操作的核心思想为:将栈顶的元素和数组最后一个元素进行交换之后,删除最后一个元素,之后再对堆进行整理(整理为最小堆或最大堆)

java">public void poll() {// 将根节点(索引0)与堆的最后一个节点交换位置swap(0, usedSize - 1);// 移除堆的最后一个节点(原根节点),减少堆的大小usedSize--;// 从根节点开始进行下沉调整,恢复堆的性质shiftDown(0, usedSize);
}private void swap(int pos1, int pos2) {// 交换堆中两个指定位置的元素int temp = elem[pos1];elem[pos1] = elem[pos2];elem[pos2] = temp;
}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(child, root);root = child; // 更新根节点为刚刚下沉的孩子节点child = 2 * root + 1; // 更新孩子节点的索引} else {break; // 当前根节点已经大于或等于所有孩子节点,结束下沉}}
}

(3)返回堆顶元素

        其核心思想为:将堆中的首元素返回

java">public boolean isEmpty() {// 检查堆是否为空// 如果堆的大小为0,则返回true,表示堆为空;否则返回falsereturn usedSize == 0;
}public int peekHeap() {// 查看堆顶元素if (isEmpty()) {// 如果堆为空,则抛出异常throw new NullElementException("优先队列中没有元素!!!");}// 返回堆顶元素(根节点)return elem[0];
}

(4)判断堆是否为空

          其核心思想为:数组中有没有元素

java">public boolean isEmpty() {// 如果 usedSize(堆的当前大小)等于0,说明堆中没有元素,返回 true。// 否则,返回 false,表示堆中至少有一个元素。return usedSize == 0;
}

        ——通过上面的讲解,我们就大致的了解了堆中的基本操作。


以上就是本篇文章的全部内容了~~~


http://www.ppmy.cn/news/1503892.html

相关文章

【DataSophon】DataSophon1.2.1 ranger usersync整合

目录 一、简介 二、实现步骤 2.1 ranger-usersync包下载编译 2.2 构建压缩包 2.3 编辑元数据文件 2.4 修改源码 三、重新安装 一、简介 如下是DDP1.2.1默认有的rangerAdmin&#xff0c; 我们需要将rangerusersync整合进来 ,实现将Linux机器上的用户和组信息同步到Ranger…

HarmonyOS应用开发者基础认证,Next版本发布后最新题库

笔者会尽量找到答案的出处&#xff0c;力求答案准确无误。有些题目答案可能有错&#xff0c;也有一些笔者实在找不到出处&#xff0c;也不知道答案的&#xff0c;如果读者发现错误或有补充建议&#xff0c;欢迎评论或私信笔者。您的每一条反馈都是宝贵的&#xff0c;能够帮助笔…

Java的逻辑控制和方法的使用介绍

前言 程序的逻辑结构一共有三种&#xff1a;顺序结构、分支结构和循环结构。顺序结构就是按代码的顺序来执行相应的指令。这里主要讲述Java的分支结构和循环结构&#xff0c;由于和C语言是有相似性的&#xff0c;所以这里只会提及不同点和注意要点~~ 注意在C语言中&#xff0c;…

java高频面试题(2024最新)

目录 一.java基础1.八大基础类型2.java三大特性3.重载和重写的区别4.pubilc、protected、(dafault)不写、private修饰符的作用范围5.和equals的区别6.hashcode()值相同&#xff0c;equals就一定为true7.为什么重写equals()&#xff0c;就要重写hashcode()?8.short s 1&#x…

深度学习环境完整安装(Python+Pycharm+Pytorch cpu版)

在这里&#xff0c;我们将引导您逐步完成深度学习环境的完整安装&#xff0c;助您踏上从Python到PyTorch的探索之旅。通过本博客&#xff0c;您将轻松掌握如何设置Python环境、使用Pycharm进行开发以及安装Pytorch&#xff0c;成为一名具备完整深度学习环境的实践者。让我们一起…

Python详细安装步骤(共十步,一步一图)_python 安装教程

1&#xff0c;进入python官网&#xff1a;https://www.python.org 2&#xff0c;进入官网后&#xff0c;点击页面头部栏 Downloads&#xff0c;会弹出下拉框&#xff0c;然后选择需要安装的电脑系统 3&#xff0c;进入Windows以后&#xff0c;选择左侧的列表&#xff0c;然后选…

【已解决】java.sql.SQLException: Access denied for user ‘root‘@‘localhost‘ (using password: YES)

java.sql.SQLException: Access denied for user rootlocalhost (using password: YES)* 这个异常通常意味着你尝试使用 root 用户和某个密码去连接 MySQL 数据库时&#xff0c;MySQL 服务器拒绝了你的连接请求。这通常是由以下几个原因引起的&#xff1a; **密码错误&#xf…

【C++】深入了解C++内存管理

个人主页&#xff1a;救赎小恶魔 欢迎大家来到小恶魔频道 好久不见&#xff0c;甚是想念 今天我们要深入讲述C内存管理 目录 1.C的内存分布 2.C/C言中动态内存管理方式 1.C语言的管理方式 2.C的管理方式 new delete 3.operator new与operator delete函数 operator …

【C++航海王:追寻罗杰的编程之路】哈希的应用——位图 | 布隆过滤器

目录 1 -> 位图 1.1 -> 位图的概念 1.2 -> 位图的应用 2 -> 布隆过滤器 2.1 -> 布隆过滤器的提出 2.2 -> 布隆过滤器的概念 2.3 -> 布隆过滤器的插入 2.4 -> 布隆过滤器的查找 2.5 -> 布隆过滤器的删除 2.6 -> 布隆过滤器的优点 2.7…

【2024版】超详细Python+Pycharm安装保姆级教程,Python+Pycharm环境配置和使用指南,看完这一篇就够了

目录 一、Python开发环境配置1.Python下载与安装二、PyCharm安装运行测试汉化1.PyCharm下载及安装2.解释器配置及项目测试3.PyCharm汉化 本文将从 Python解释器安装到Pycharm专业版安装和配置汉化等使用都进行了详细介绍&#xff0c;希望能够帮助到大家。 Python解释器&Py…

【Java】了解异常

初始异常 我们平时应该已经接触过一些 “异常” 了&#xff0c;这里列举一些例子。 算术异常&#xff1a; 数组下标越界异常&#xff1a; 访问空指针异常&#xff1a; 所谓异常指的就是程序在 运行时 出现错误时通知调用者的一种机制。 异常的基本用法 捕获异常 try{ 有可能…

python GUI开发: tkinter选项卡,移动滑块,颜色选择框,文本对话框,对话输入框,通用消息框模块用法详解

✨✨ 欢迎大家来到景天科技苑✨✨ &#x1f388;&#x1f388; 养成好习惯&#xff0c;先赞后看哦~&#x1f388;&#x1f388; &#x1f3c6; 作者简介&#xff1a;景天科技苑 &#x1f3c6;《头衔》&#xff1a;大厂架构师&#xff0c;华为云开发者社区专家博主&#xff0c;…

Python|Windows 系统安装 triton 的方法

问题现象 若未安装&#xff0c;则在运行调用了该仓库的 Python 脚本时&#xff0c;会报错如下&#xff1a; ModuleNotFoundError: No module named triton在 Windows 系统中&#xff0c;如果直接使用 pip 安装&#xff0c;会报错如下&#xff1a; pip install tritonERROR: …

C# 关于 PaddleOCRSharp OCR识别的疲劳测试

目录 关于 PaddleOCRSharp 应用范例演示 ​范例运行环境 疲劳测试 添加组件库 方法设计 调用示例 小结 关于 PaddleOCRSharp PaddleOCRSharp 是百度飞桨封装的.NET版本 OCR dll 类库&#xff0c;OCR&#xff08;Optical Character Recognition&#xff09;工具可以将…

2024年Java后端学习路线

思维导图&#xff1a; 必备知识&#xff1a; Java基础 JavaWeb 数据库&#xff1a;MySql&#xff0c;Redis 开发中间件&#xff1a;Maven &#xff0c;Git &#xff0c;Docker&#xff0c;RabbitMQ 开发框架&#xff1a;SSM&#xff0c;spring boot&#xff0c;mybatis-plus、s…

Matlab从图(fig)中提取数据

1. 根据Matlab生成的图提取其中数据 在数据分析和处理过程中&#xff0c;我们经常需要从图像中提取有用的数据。Matlab作为一个强大的数据分析工具&#xff0c;提供了丰富的图像处理函数&#xff0c;可以帮助我们从图像中提取数据。本文将介绍如何在Matlab中提取图中数据的方法…

matlab simulink 中 To Workspace 使用详解

matlab simulink 中 To Workspace 使用详解 当simulink中有数据想要导出使用时可以搜索&#xff1a; To workspace模块 当不想要out这个前缀时&#xff0c;可以在设置中按如图所示设置 模块中属性的功能介绍 ①变量名称&#xff1a;输出到工作空间中变量的名称&#xff0c;用…

Java 反射机制 -- Java 语言反射的概述、核心类与高级应用

大家好&#xff0c;我是栗筝i&#xff0c;这篇文章是我的 “栗筝i 的 Java 技术栈” 专栏的第 010 篇文章&#xff0c;在 “栗筝i 的 Java 技术栈” 这个专栏中我会持续为大家更新 Java 技术相关全套技术栈内容。专栏的主要目标是已经有一定 Java 开发经验&#xff0c;并希望进…

VSCode 配置python虚拟环境(激活环境细节)_vscode python conda虚拟环境(1)

Anaconda Prompt常用命令&#xff1a; 1.查看存在的环境&#xff1a;conda info -e 2.创建新环境&#xff1a;conda create -n 环境名 python&#xff08;python的版本号&#xff09; 3.切换到某个环境&#xff1a;conda activate 环境名 4.查看环境中已安装的包&#xff1a;co…

【C语言】结构体,枚举,联合,位段等自定义类型详细介绍

目录 结构体 结构体声明 结构体成员的访问 结构体自引用 结构体变量定义&#xff0c;初始化&#xff0c;传参 结构体内存对齐 位段 枚举 联合(共用体) 结构体 1. 结构体声明 1.1 概念 1. 结构体是一些值的集合&#xff0c;这些值称为成员变量。 2. 结构体的每个成…