如何构建最小堆?
方式1:上浮调整
/*** 上浮调整(小的上浮)*/
public static void smallUp1(int[] arr, int child) {int parent = (child - 1) / 2;while (0 < child && arr[child] < arr[parent]) { // 0 < child说明这个节点还是叶子arr[child] = arr[child] ^ arr[parent];arr[parent] = arr[child] ^ arr[parent];arr[child] = arr[child] ^ arr[parent];child = parent; // 父节点此时开始视为子节点parent = (child - 1) / 2; // 算父节点的父节点}
}
/*** 上浮调整(小的上浮)*/
public static void smallUp2(int[] arr, int child) {int parent = (child - 1) / 2;int baseVal = arr[child]; // 把处理的数据取出来while (0 < child && baseVal < arr[parent]) {arr[child] = arr[parent]; // 父节点值挪下来,父节点为baseVal备选位置child = parent;parent = (child - 1) / 2;}arr[child] = baseVal; // baseVal上浮不动了,所以落在当前子节点位置
}
方式2:下沉调整
/*** 下浮调整(大的下沉)** @param arr 待调整的堆* @param parent 要下沉的父节点* @param length 堆的有效大小*/
public static void bigDown1(int[] arr, int parent, int length) {int child = 2 * parent + 1;while (child < length) { // 范围内if (child + 1 < length && arr[child + 1] < arr[child]) { // 取出两个子节点值最小的那个child++;}if (arr[parent] <= arr[child]) { // 父节点比他们都小,则符合预期终止循环break;}arr[child] = arr[child] ^ arr[parent];arr[parent] = arr[child] ^ arr[parent];arr[child] = arr[child] ^ arr[parent];parent = child; // 此时子节点视为父节点继续下一步处理child = 2 * child + 1;}
}
/*** 下浮调整(大的下沉)** @param arr 待调整的堆* @param parent 要下沉的父节点* @param length 堆的有效大小*/
public static void bigDown2(int[] arr, int parent, int length) {int baseVal = arr[parent];int child = 2 * parent + 1;while (child < length) {if (child + 1 < length && arr[child + 1] < arr[child]) {child++;}if (baseVal <= arr[child]) {break;}arr[parent] = arr[child]; // 子节点小,则子节点位置上移parent = child;child = 2 * child + 1;}arr[parent] = baseVal; // baseVal下沉不动了,所以落在当前子节点位置
}
构建最小堆
int[] arr = {1, 3, 2, 9, 5, 7, 8, 6, 10, 0};System.out.println("原始数据:" + Arrays.toString(arr));
for (int i = arr.length - 1; i >= 0; i--) {smallUp1(arr, i);
}
System.out.println("上浮构建最小二叉堆:" + Arrays.toString(arr));int[] arr2 = {1, 3, 2, 9, 5, 7, 8, 6, 10, 0};
for (int i = arr2.length - 1; i >= 0; i--) {smallUp1(arr2, i);
}
System.out.println("上浮构建最小二叉堆:" + Arrays.toString(arr2));int[] arr11 = {1, 3, 2, 9, 5, 7, 8, 6, 10, 0};
for (int i = (arr11.length - 1) / 2; i >= 0; i--) {bigDown1(arr11, i, arr11.length);
}
System.out.println("下沉构建最小二叉堆:" + Arrays.toString(arr11));int[] arr22 = {1, 3, 2, 9, 5, 7, 8, 6, 10, 0};
for (int i = (arr22.length - 1) / 2; i >= 0; i--) {bigDown2(arr22, i, arr22.length);
}
System.out.println("下沉构建最小二叉堆:" + Arrays.toString(arr22));原始数据:[1, 3, 2, 9, 5, 7, 8, 6, 10, 0]
上浮构建最小二叉堆:[0, 1, 2, 6, 3, 7, 8, 9, 10, 5]
上浮构建最小二叉堆:[0, 1, 2, 6, 3, 7, 8, 9, 10, 5]
下沉构建最小二叉堆:[0, 1, 2, 6, 3, 7, 8, 9, 10, 5]
下沉构建最小二叉堆:[0, 1, 2, 6, 3, 7, 8, 9, 10, 5]
相关文章:
如何构建最小堆?
方式1:上浮调整 /*** 上浮调整(小的上浮)*/ public static void smallUp1(int[] arr, int child) {int parent (child - 1) / 2;while (0 < child && arr[child] < arr[parent]) { // 0 < child说明这个节点还是叶子arr[child] arr[child] ^ ar…...
基于Netty实现安全认证的WebSocket(wss)客户端
1.Netty服务端 服务端代码参考【基于Netty实现安全认证的WebSocket(wss)服务端-CSDN博客】 2.Netty客户端 客户端代码参考【基于Netty实现WebSocket客户端-CSDN博客】中两种都可以;这里用的是第一种。 新增SslHandler的代码: …...
代码随想录算法训练营第四十四天 | 01背包问题 二维、 01背包问题 一维、416. 分割等和子集
01背包问题 二维 代码随想录 视频讲解:带你学透0-1背包问题!| 关于背包问题,你不清楚的地方,这里都讲了!| 动态规划经典问题 | 数据结构与算法_哔哩哔哩_bilibili 1.dp数组定义 dp[i][j] 下标为[0,i]之间的物品&…...
redis常见使用场景
文章目录 redis常见使用场景全局ID位统计购物车用户消息时间线timeline抽奖商品筛选分布式锁限流redis实现计数器排行榜消息队列redis 如何实现延时队列 redis生产常用的场景 redis常见使用场景 Redis 是一种高性能的内存数据库,广泛应用于各种场景中。以下是 Redi…...
模糊C均值(FCM)算法更新公式推导
模糊C均值(FCM)算法更新公式推导 目标函数 FCM的目标函数为: J m ∑ i 1 n ∑ j 1 k u i j m ∥ x i − c j ∥ 2 J_m \sum_{i1}^n \sum_{j1}^k u_{ij}^m \|x_i - c_j\|^2 Jmi1∑nj1∑kuijm∥xi−cj∥2 其中: …...
金融创新浪潮下的拆分盘投资探索
随着数字化时代的步伐加速,金融领域正经历着前所未有的变革。在众多金融创新中,拆分盘作为一种新兴的投资模式,以其独特的增长机制,吸引了投资者的广泛关注。本文将对拆分盘的投资逻辑进行深入剖析,并结合具体案例&…...
一份不知道哪里来的第十五届国赛模拟题
这是一个不知道来源的模拟题目,没有完全完成,只作代码记录,不作分析和展示,极其冗长,但里面有长按短按双击的复合,可以看看。 目录 题目代码底层驱动主程序核心代码关键:双击单击长按复合代码 …...
机器人动力学模型与MATLAB仿真
机器人刚体动力学由以下方程控制!!! startup_rvc mdl_puma560 p560.dyn 提前计算出来这些“disturbance”,然后在控制环路中将它“抵消”(有时候也叫前馈控制) 求出所需要的力矩,其中M项代表克服…...
SAPUI5基础知识3 - 引导过程(Bootstrap)
1. 背景 在上一篇博客中,我们已经建立出了第一个SAPUI5项目,接下来,我们将为这个项目添加引导过程。 在动手练习之前,让我们先解释一下什么引导过程。 1.1 什么是引导过程? 在计算机科学中,引导过程也称…...
ABAP 借助公司封装的钉钉URL,封装的RFC给钉钉发送消息
FUNCTION ZRFC_BC_SMSSEND_DINGTALK. *"---------------------------------------------------------------------- *"*"本地接口: *" IMPORTING *" VALUE(DESTUSRID) TYPE CHAR255 *" VALUE(CONTENT) TYPE CHAR255 *&quo…...
登录校验及全局异常处理器
登录校验 会话技术 会话:用户打开浏览器,访问web服务器的资源,会话建立,直到有一方断开连接,会话结束.在一次会话中可以包含多次请求和响应会话跟踪:一种维护浏览器状态的方法,服务器需要识别多次请求是否来自于同一浏览器,以便在同一次会话请求间共享数据会话跟踪方案 客户端…...
计算机视觉与模式识别实验1-2 图像的形态学操作
文章目录 🧡🧡实验流程🧡🧡1.图像膨胀2.图像腐蚀3.膨胀与腐蚀的综合使用4.对下面二值图像的目标提取骨架,并分析骨架结构。 🧡🧡全部代码🧡🧡 🧡🧡…...
【前端每日基础】day31——uni-app
uni-app 开发详细介绍 基本概念 uni-app:uni-app 是一个使用 Vue.js 开发多端应用的框架,可以编译到微信小程序、支付宝小程序、百度小程序、字节跳动小程序、H5、App等多个平台。 跨平台:一次开发,多端部署。通过条件编译实现多…...
云动态摘要 2024-05-31
给您带来云厂商的最新动态,最新产品资讯和最新优惠更新。 最新优惠与活动 [1.5折起]年中盛惠--AI分会场 腾讯云 2024-05-30 人脸核身、语音识别、文字识别、数智人、腾讯混元等热门AI产品特惠,1.5折起 云服务器ECS试用产品续用 阿里云 2024-04-14 云…...
Oracle数据块如何存储真实数据
上周休假了几天,颓废了,没有输出。今天写一点内容。 先抛出一个问题。表中的数据在Oracle数据块中是如何存储的呢?今天简单说一下这个问题。通常数据库中的表会存储字符,数字,日期 这3种常见的数据类型。下面的例子就用这3种数据类型作说明 首先,Oracle数据块底层存储这…...
【WEB前端2024】开源智体世界:乔布斯3D纪念馆-第30课-门的移动动画
【WEB前端2024】开源智体世界:乔布斯3D纪念馆-第30课-门的移动动画 使用dtns.network德塔世界(开源的智体世界引擎),策划和设计《乔布斯超大型的开源3D纪念馆》的系列教程。dtns.network是一款主要由JavaScript编写的智体世界引擎…...
智能化改造给企业带来的实际效果
1. 提高生产效率:通过自动化和智能化的生产线,减少人工操作,显著提升单位时间内的生产量。 2. 提升产品质量:智能化改造通过精确控制生产过程,减少人为错误,提高产品的一致性和可靠性。 3. 降低生产成本&am…...
深度学习-语言模型
深度学习-语言模型 统计语言模型神经网络语言模型语言模型的应用序列模型(Sequence Model)语言模型(Language Model)序列模型和语言模型的区别 语言模型(Language Model)是自然语言处理(NLP&…...
微型导轨在自动化制造中有哪些优势?
微型导轨在自动化制造中发挥重要作用,能够满足自动化设备制造中对精度要求较高的工艺环节。适用于自动装配线、自动检测设备和机器人操作等环节,推动了行业的进步与发展。那么,微型导轨在使用中有哪些优势呢? 1、精度高和稳定性强…...
探索气象数据的多维度三维可视化:PM2.5、风速与高度分析
探索气象数据的多维度可视化:PM2.5、风速与高度分析 摘要 在现代气象学中,数据可视化是理解复杂气象模式和趋势的关键工具。本文将介绍一种先进的数据可视化技术,它能够将PM2.5浓度、风速和高度等多维度数据以直观和动态的方式展现出来。 …...
Oracle查询表空间大小
1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...
线程与协程
1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指:像函数调用/返回一样轻量地完成任务切换。 举例说明: 当你在程序中写一个函数调用: funcA() 然后 funcA 执行完后返回&…...
学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1
每日一言 生活的美好,总是藏在那些你咬牙坚持的日子里。 硬件:OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写,"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...
【配置 YOLOX 用于按目录分类的图片数据集】
现在的图标点选越来越多,如何一步解决,采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集(每个目录代表一个类别,目录下是该类别的所有图片),你需要进行以下配置步骤&#x…...
2025盘古石杯决赛【手机取证】
前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来,实在找不到,希望有大佬教一下我。 还有就会议时间,我感觉不是图片时间,因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...
python执行测试用例,allure报乱码且未成功生成报告
allure执行测试用例时显示乱码:‘allure’ �����ڲ����ⲿ���Ҳ���ǿ�&am…...
服务器--宝塔命令
一、宝塔面板安装命令 ⚠️ 必须使用 root 用户 或 sudo 权限执行! sudo su - 1. CentOS 系统: yum install -y wget && wget -O install.sh http://download.bt.cn/install/install_6.0.sh && sh install.sh2. Ubuntu / Debian 系统…...
代码随想录刷题day30
1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...
面向无人机海岸带生态系统监测的语义分割基准数据集
描述:海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而,目前该领域仍面临一个挑战,即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...
Qemu arm操作系统开发环境
使用qemu虚拟arm硬件比较合适。 步骤如下: 安装qemu apt install qemu-system安装aarch64-none-elf-gcc 需要手动下载,下载地址:https://developer.arm.com/-/media/Files/downloads/gnu/13.2.rel1/binrel/arm-gnu-toolchain-13.2.rel1-x…...
