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

        前言:(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)逐个插入元素

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

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)批量建堆

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

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)插入操作

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

// 插入元素的方法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)删除操作

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

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)返回堆顶元素

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

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

(4)判断堆是否为空

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

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

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


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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/389466.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

微信小程序-获取手机号:HttpClientErrorException: 412 Precondition Failed: [no body]

问题&#xff1a; 412 异常就是你的请求参数获取请求头与服务器的不符&#xff0c;缺少请求体&#xff01; 我的问题&#xff1a; 我这里获取微信手机号的时候突然给我报错142&#xff0c;但是代码用的是原来的代码&#xff0c;换了一个框架就噶了&#xff01; 排查问题&am…

Springboot手工艺品交易平台—计算机毕业设计源码11541

摘 要 信息化社会内需要与之针对性的信息获取途径&#xff0c;但是途径的扩展基本上为人们所努力的方向&#xff0c;由于站在的角度存在偏差&#xff0c;人们经常能够获得不同类型信息&#xff0c;这也是技术最为难以攻克的课题。针对手工艺品交易平台等问题&#xff0c;对手工…

【MySQL进阶】事务隔离级别 MVCC

目录 MySQL事务隔离级别 1. 读未提交&#xff08;Read Uncommitted&#xff09; 2. 读已提交&#xff08;Read Committed&#xff09; 3. 可重复读&#xff08;Repeatable Read&#xff09;(默认隔离级别) 4. 串行化&#xff08;Serializable&#xff09; 表格总结 MVCC …

抖音爬虫-批量下载主页作品

使用说明 config.ini是配置文件&#xff0c;可配置文件名规则、下载视频图文音乐等。 DownloadList.txt是批量下载清单&#xff0c;可配置批量下载类型和地址。 打开软件&#xff0c;选择对应的功能&#xff0c;第一次扫码登录&#xff08;后续可自动加载cookie登录&#xff…

揭秘循环购模式:消费即收益

大家好&#xff0c;我是你们的电商策略顾问吴军。今天&#xff0c;我将带大家深入探索一种别开生面的商业模式——循环购模式。这种模式究竟有何魅力&#xff0c;能让消费者在享受购物乐趣的同时&#xff0c;还能获得额外的收益&#xff1f;更有趣的是&#xff0c;一些商家通过…

区块链软硬件协同,做产业数字化转型的“安全官” |《超话区块链》直播预告

今年的两会政府工作报告提出&#xff1a;“产业的数字化&#xff08;行业数字化转型&#xff09;是发展新质生产力的核心&#xff0c;是推动产业升级实现高质量发展的关键。”全面推进产业数字化&#xff0c;需要技术创新与产业应用深入协同&#xff1b;立足可持续发展的长远目…

Java面试八股之简述spring boot的目录结构

简述spring boot的目录结构 Spring Boot 项目遵循标准的 Maven 或 Gradle 项目布局&#xff0c;并且有一些约定的目录用于组织不同的项目组件。下面是一个典型的 Spring Boot 项目目录结构&#xff1a; src/main/java&#xff1a;包含所有的 Java 源代码&#xff0c;通常按包组…

OpenCV仿射变换实现图像扭曲与旋转

目录 1. 仿射变换 2. 仿射变换的求解 3. 代码实现 3.1 图像扭曲 3.2 图像旋转 参考内容 1. 仿射变换 仿射变换是一种可以表达为乘以一个矩阵&#xff08;线性变换&#xff09;再加上一个向量&#xff08;平移&#xff09;的变换。在几何中&#xff0c;就是将一个向量空间…

Hive环境搭建(Mysql数据库)

【实验目的】 1) 了解hive的作用 2) 熟练hive的配置过程&#xff08;Mysql数据库&#xff09; 【实验原理】 Hive工具中默认使用的是derby数据库&#xff0c;该数据库使用简单&#xff0c;操作灵活&#xff0c;但是存在一定的局限性&#xff0c;hive支持使用第三方数据库&…

Umi-OCR:功能强大且易于使用的本地照片识别软件

Umi-OCR是一款开源且免费的离线OCR&#xff08;光学字符识别&#xff09;软件&#xff0c;可让您轻松从照片中提取文本。它支持多种语言&#xff0c;并具有许多其他功能使其成为照片识别任务的绝佳选择。 Umi-OCR的优势 离线操作&#xff1a; Umi-OCR无需互联网连接即可工作&…

html+css 实现文字滚动的按钮

前言&#xff1a;哈喽&#xff0c;大家好&#xff0c;今天给大家分享htmlcss 绚丽效果&#xff01;并提供具体代码帮助大家深入理解&#xff0c;彻底掌握&#xff01;创作不易&#xff0c;如果能帮助到大家或者给大家一些灵感和启发&#xff0c;欢迎收藏关注哦 &#x1f495; 文…

手摸手教你前端和后端是如何实现导出 Excel 的?

前言 大家好呀&#xff0c;我是雪荷。在上篇文章&#xff08;EasyExcel 初使用—— Java 实现多种写入 Excel 功能-CSDN博客&#xff09;中给大家介绍了 Java 是如何写入 Excel 的&#xff0c;那么这篇算是对上篇文章的拓展&#xff0c;主要介绍前端和后端分别是如何导出数据至…

代码随想录训练营 Day18打卡 二叉树 part06 530. 二叉搜索树的最小绝对差 501. 二叉搜索树中的众数 236. 二叉树的最近公共祖先

代码随想录训练营 Day18打卡 二叉树 part06 一、 力扣530. 二叉搜索树的最小绝对差 给你一个二叉搜索树的根节点 root &#xff0c;返回 树中任意两不同节点值之间的最小差值 。 差值是一个正数&#xff0c;其数值等于两值之差的绝对值。 示例 &#xff1a; 输入&#xff1a; …

spring boot + vue3 接入钉钉实现扫码登录

1&#xff1a;准备工作 1.1&#xff1a;进入钉钉开放平台创建开发者应用。应用创建和类型介绍&#xff0c;参考下方。 应用类型介绍 - 钉钉开放平台 (dingtalk.com) 应用能力介绍 - 钉钉开放平台 (dingtalk.com) 扫码登录第三方网站 - 钉钉开放平台 (dingtalk.com) 1.2&…

KaiwuDB 产品总监李月飞:让中国物联网用上放心的数据库产品

​2024年7月17日&#xff0c;KaiwuDB 产品总监李月飞受邀于 2024 可信数据库发展大会“能源与政务数据库应用创新”分论坛发表演讲。以下是李月飞主题演讲《深耕数据良田&#xff0c;KaiwuDB 洞见能源产业数字新生力》精华实录。 数据&#xff0c;给能源变革带来新的可能 众所…

TypeScript 简介

文档 typeScript官网中文文档&#xff1a;https://www.tslang.cn/index.html中文文档(简洁点)&#xff1a;https://typescript.bootcss.comMDN 前言 JavaScript 引入编程社区已有 20 多年&#xff0c;如今已成为有史以来使用最广泛的跨平台语言之一。JavaScript 最初是一种用…

SSL VPN详细概述

为什么会出现SSL VPN呢&#xff1f;在这之前不是有IPSEC VPN吗&#xff1f; 通过这两个问题我们可以发现多半是IPSEC VPN在某些方面肯定有所欠缺&#xff0c;所以后面在出现了SSL VPN。 之前说过根据组网方式划分&#xff0c;可以分为 client to LAN 和 LAN to LAN 两种 而…

CTF学习笔记汇总(非常详细)零基础入门到精通,收藏这一篇就够了

CTF学习笔记汇总 Part.01 Web 01 SSRF 主要攻击方式如下&#xff1a; 01 对外网、服务器所在内网、本地进行端口扫描&#xff0c;获取一些服务的banner信息。 02 攻击运行在内网或本地的应用程序。 03 对内网Web应用进行指纹识别&#xff0c;识别企业内部的资产信息。 …

深入分析 Android ContentProvider (十二)

文章目录 深入分析 Android ContentProvider (十二)Android 中 ContentProvider 的系统代码分析&#xff08;续&#xff09;1. ContentProvider 的内部实现机制1.1. ContentProvider 的创建与生命周期管理1.2. ContentProvider 的数据访问与处理1.3. ContentProvider 的权限管理…

Go语言---sync.WaitGroup

在Go语言中&#xff0c;给我们提供了用于线程同步的sync.WaitGroup&#xff0c;简单来讲&#xff0c;WaitGroup就是指等待一组&#xff0c;等待一个系列执行完成后才会继续向下执行。 WaitGroup数据结构 type WaitGroup struct {noCopy noCopystate atomic.Uint64 // 高 32 b…