当前位置: 首页 > news >正文

如何构建最小堆?

方式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&#xff1a;上浮调整 /*** 上浮调整(小的上浮)*/ 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&#xff08;wss&#xff09;服务端-CSDN博客】 2.Netty客户端 客户端代码参考【基于Netty实现WebSocket客户端-CSDN博客】中两种都可以&#xff1b;这里用的是第一种。 新增SslHandler的代码&#xff1a; …...

代码随想录算法训练营第四十四天 | 01背包问题 二维、 01背包问题 一维、416. 分割等和子集

01背包问题 二维 代码随想录 视频讲解&#xff1a;带你学透0-1背包问题&#xff01;| 关于背包问题&#xff0c;你不清楚的地方&#xff0c;这里都讲了&#xff01;| 动态规划经典问题 | 数据结构与算法_哔哩哔哩_bilibili 1.dp数组定义 dp[i][j] 下标为[0,i]之间的物品&…...

redis常见使用场景

文章目录 redis常见使用场景全局ID位统计购物车用户消息时间线timeline抽奖商品筛选分布式锁限流redis实现计数器排行榜消息队列redis 如何实现延时队列 redis生产常用的场景 redis常见使用场景 Redis 是一种高性能的内存数据库&#xff0c;广泛应用于各种场景中。以下是 Redi…...

模糊C均值(FCM)算法更新公式推导

模糊C均值&#xff08;FCM&#xff09;算法更新公式推导 目标函数 FCM的目标函数为&#xff1a; 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 Jm​i1∑n​j1∑k​uijm​∥xi​−cj​∥2 其中&#xff1a; …...

金融创新浪潮下的拆分盘投资探索

随着数字化时代的步伐加速&#xff0c;金融领域正经历着前所未有的变革。在众多金融创新中&#xff0c;拆分盘作为一种新兴的投资模式&#xff0c;以其独特的增长机制&#xff0c;吸引了投资者的广泛关注。本文将对拆分盘的投资逻辑进行深入剖析&#xff0c;并结合具体案例&…...

一份不知道哪里来的第十五届国赛模拟题

这是一个不知道来源的模拟题目&#xff0c;没有完全完成&#xff0c;只作代码记录&#xff0c;不作分析和展示&#xff0c;极其冗长&#xff0c;但里面有长按短按双击的复合&#xff0c;可以看看。 目录 题目代码底层驱动主程序核心代码关键&#xff1a;双击单击长按复合代码 …...

机器人动力学模型与MATLAB仿真

机器人刚体动力学由以下方程控制&#xff01;&#xff01;&#xff01; startup_rvc mdl_puma560 p560.dyn 提前计算出来这些“disturbance”&#xff0c;然后在控制环路中将它“抵消”&#xff08;有时候也叫前馈控制&#xff09; 求出所需要的力矩&#xff0c;其中M项代表克服…...

SAPUI5基础知识3 - 引导过程(Bootstrap)

1. 背景 在上一篇博客中&#xff0c;我们已经建立出了第一个SAPUI5项目&#xff0c;接下来&#xff0c;我们将为这个项目添加引导过程。 在动手练习之前&#xff0c;让我们先解释一下什么引导过程。 1.1 什么是引导过程&#xff1f; 在计算机科学中&#xff0c;引导过程也称…...

ABAP 借助公司封装的钉钉URL,封装的RFC给钉钉发送消息

FUNCTION ZRFC_BC_SMSSEND_DINGTALK. *"---------------------------------------------------------------------- *"*"本地接口&#xff1a; *" IMPORTING *" VALUE(DESTUSRID) TYPE CHAR255 *" VALUE(CONTENT) TYPE CHAR255 *&quo…...

登录校验及全局异常处理器

登录校验 会话技术 会话:用户打开浏览器,访问web服务器的资源,会话建立,直到有一方断开连接,会话结束.在一次会话中可以包含多次请求和响应会话跟踪:一种维护浏览器状态的方法,服务器需要识别多次请求是否来自于同一浏览器,以便在同一次会话请求间共享数据会话跟踪方案 客户端…...

计算机视觉与模式识别实验1-2 图像的形态学操作

文章目录 &#x1f9e1;&#x1f9e1;实验流程&#x1f9e1;&#x1f9e1;1.图像膨胀2.图像腐蚀3.膨胀与腐蚀的综合使用4.对下面二值图像的目标提取骨架&#xff0c;并分析骨架结构。 &#x1f9e1;&#x1f9e1;全部代码&#x1f9e1;&#x1f9e1; &#x1f9e1;&#x1f9e1…...

【前端每日基础】day31——uni-app

uni-app 开发详细介绍 基本概念 uni-app&#xff1a;uni-app 是一个使用 Vue.js 开发多端应用的框架&#xff0c;可以编译到微信小程序、支付宝小程序、百度小程序、字节跳动小程序、H5、App等多个平台。 跨平台&#xff1a;一次开发&#xff0c;多端部署。通过条件编译实现多…...

云动态摘要 2024-05-31

给您带来云厂商的最新动态&#xff0c;最新产品资讯和最新优惠更新。 最新优惠与活动 [1.5折起]年中盛惠--AI分会场 腾讯云 2024-05-30 人脸核身、语音识别、文字识别、数智人、腾讯混元等热门AI产品特惠&#xff0c;1.5折起 云服务器ECS试用产品续用 阿里云 2024-04-14 云…...

Oracle数据块如何存储真实数据

上周休假了几天,颓废了,没有输出。今天写一点内容。 先抛出一个问题。表中的数据在Oracle数据块中是如何存储的呢?今天简单说一下这个问题。通常数据库中的表会存储字符,数字,日期 这3种常见的数据类型。下面的例子就用这3种数据类型作说明 首先,Oracle数据块底层存储这…...

【WEB前端2024】开源智体世界:乔布斯3D纪念馆-第30课-门的移动动画

【WEB前端2024】开源智体世界&#xff1a;乔布斯3D纪念馆-第30课-门的移动动画 使用dtns.network德塔世界&#xff08;开源的智体世界引擎&#xff09;&#xff0c;策划和设计《乔布斯超大型的开源3D纪念馆》的系列教程。dtns.network是一款主要由JavaScript编写的智体世界引擎…...

智能化改造给企业带来的实际效果

1. 提高生产效率&#xff1a;通过自动化和智能化的生产线&#xff0c;减少人工操作&#xff0c;显著提升单位时间内的生产量。 2. 提升产品质量&#xff1a;智能化改造通过精确控制生产过程&#xff0c;减少人为错误&#xff0c;提高产品的一致性和可靠性。 3. 降低生产成本&am…...

深度学习-语言模型

深度学习-语言模型 统计语言模型神经网络语言模型语言模型的应用序列模型&#xff08;Sequence Model&#xff09;语言模型&#xff08;Language Model&#xff09;序列模型和语言模型的区别 语言模型&#xff08;Language Model&#xff09;是自然语言处理&#xff08;NLP&…...

微型导轨在自动化制造中有哪些优势?

微型导轨在自动化制造中发挥重要作用&#xff0c;能够满足自动化设备制造中对精度要求较高的工艺环节。适用于自动装配线、自动检测设备和机器人操作等环节&#xff0c;推动了行业的进步与发展。那么&#xff0c;微型导轨在使用中有哪些优势呢&#xff1f; 1、精度高和稳定性强…...

探索气象数据的多维度三维可视化:PM2.5、风速与高度分析

探索气象数据的多维度可视化&#xff1a;PM2.5、风速与高度分析 摘要 在现代气象学中&#xff0c;数据可视化是理解复杂气象模式和趋势的关键工具。本文将介绍一种先进的数据可视化技术&#xff0c;它能够将PM2.5浓度、风速和高度等多维度数据以直观和动态的方式展现出来。 …...

React Native 导航系统实战(React Navigation)

导航系统实战&#xff08;React Navigation&#xff09; React Navigation 是 React Native 应用中最常用的导航库之一&#xff0c;它提供了多种导航模式&#xff0c;如堆栈导航&#xff08;Stack Navigator&#xff09;、标签导航&#xff08;Tab Navigator&#xff09;和抽屉…...

三维GIS开发cesium智慧地铁教程(5)Cesium相机控制

一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点&#xff1a; 路径验证&#xff1a;确保相对路径.…...

Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)

文章目录 1.什么是Redis&#xff1f;2.为什么要使用redis作为mysql的缓存&#xff1f;3.什么是缓存雪崩、缓存穿透、缓存击穿&#xff1f;3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...

DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI

前一阵子在百度 AI 开发者大会上&#xff0c;看到基于小智 AI DIY 玩具的演示&#xff0c;感觉有点意思&#xff0c;想着自己也来试试。 如果只是想烧录现成的固件&#xff0c;乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外&#xff0c;还提供了基于网页版的 ESP LA…...

LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf

FTP 客服管理系统 实现kefu123登录&#xff0c;不允许匿名访问&#xff0c;kefu只能访问/data/kefu目录&#xff0c;不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...

Razor编程中@Html的方法使用大全

文章目录 1. 基础HTML辅助方法1.1 Html.ActionLink()1.2 Html.RouteLink()1.3 Html.Display() / Html.DisplayFor()1.4 Html.Editor() / Html.EditorFor()1.5 Html.Label() / Html.LabelFor()1.6 Html.TextBox() / Html.TextBoxFor() 2. 表单相关辅助方法2.1 Html.BeginForm() …...

Web中间件--tomcat学习

Web中间件–tomcat Java虚拟机详解 什么是JAVA虚拟机 Java虚拟机是一个抽象的计算机&#xff0c;它可以执行Java字节码。Java虚拟机是Java平台的一部分&#xff0c;Java平台由Java语言、Java API和Java虚拟机组成。Java虚拟机的主要作用是将Java字节码转换为机器代码&#x…...

MySQL 索引底层结构揭秘:B-Tree 与 B+Tree 的区别与应用

文章目录 一、背景知识&#xff1a;什么是 B-Tree 和 BTree&#xff1f; B-Tree&#xff08;平衡多路查找树&#xff09; BTree&#xff08;B-Tree 的变种&#xff09; 二、结构对比&#xff1a;一张图看懂 三、为什么 MySQL InnoDB 选择 BTree&#xff1f; 1. 范围查询更快 2…...

Rust 开发环境搭建

环境搭建 1、开发工具RustRover 或者vs code 2、Cygwin64 安装 https://cygwin.com/install.html 在工具终端执行&#xff1a; rustup toolchain install stable-x86_64-pc-windows-gnu rustup default stable-x86_64-pc-windows-gnu ​ 2、Hello World fn main() { println…...

Kubernetes 网络模型深度解析:Pod IP 与 Service 的负载均衡机制,Service到底是什么?

Pod IP 的本质与特性 Pod IP 的定位 纯端点地址&#xff1a;Pod IP 是分配给 Pod 网络命名空间的真实 IP 地址&#xff08;如 10.244.1.2&#xff09;无特殊名称&#xff1a;在 Kubernetes 中&#xff0c;它通常被称为 “Pod IP” 或 “容器 IP”生命周期&#xff1a;与 Pod …...