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

数据结构——堆（介绍，堆的基本操作、堆排序）

news 来源：原创 2025/5/28 7:39:32

我是一个计算机专业研0的学生卡蒙Camel🐫🐫🐫（刚保研）
记录每天学习过程（主要学习Java、python、人工智能），总结知识点（内容来自：自我总结+网上借鉴）
希望大家能一起发现问题和补充，也欢迎讨论👏👏👏

堆

堆的介绍

堆是一种特殊的树形数据结构，通常以完全二叉树的形式表示，并且满足堆属性。根据堆属性的不同，堆可以分为两种类型：

最大堆（Max Heap）：对于每个节点，它的值都大于或等于其子节点的值。因此，堆顶元素（根节点）总是最大的。
最小堆（Min Heap）：对于每个节点，它的值都小于或等于其子节点的值。因此，堆顶元素（根节点）总是最小的。

堆存储

（二叉）堆可以用完全二叉树的形式进行存储。
树中任意节点 i，其左子节点序号为 2*i，右子节点序号为 2*i+1

堆操作

堆插入

将要插入的元素放到最后
从底向上，如果父结点比该元素小，则该节点和父结点交换，直到无法交换

删除堆顶

删除对顶元素是最大堆(最小堆)的最大值(最小值)，为了保持堆的性质，需要对堆的结构进行调整，我们将这个过程称之为"堆化"，有两种方法：

自底向上的堆化
自顶向下堆化

自底向上堆化

以大顶堆为例：

先删除堆顶元素(即数组中index = 1的位置)
比较根结点的左子节点和右子节点(index = 2和3)，较大的元素放到根节点
此时又有空位，和步骤2一样，空位两个子节点较大的移动到空位，直到最底部

自顶向下堆化

我们将最后一个元素移动到堆顶。
不停与左右子节点的值进行比较，和较大的子节点交换位置，直到无法交换位置。

堆排序

堆排序分为两个步骤：

建堆
排序

1. 建堆

建堆需要对所有非叶节点的自顶向下堆化。

顺序是从index=n/2到index=1依次进行堆化

引用JavaGuide的图：

一开始没排序前的数组（n = 6，所以要从索引为 3 到 1 的顺序进行堆化）：

对index=3的节点进行堆化：

对index=2的节点进行堆化

对index=1的节点进行堆化，堆化完成

2. 排序

我们在第一步已经建堆完毕，故堆顶元素就是最大值。所以我们重复取出堆顶元素，将这个最大的堆顶元素放至数组末尾，并对剩下的元素进行堆化即可。

取出堆顶元素并且堆化

一次取出堆顶并且优化

数据结构——堆（介绍，堆的基本操作、堆排序）

我是一个计算机专业研0的学生卡蒙Camel🐫🐫🐫（刚保研） 记录每天学习过程（主要学习Java、python、人工智能），总结知识点（内容来自：自我总结网上借鉴&#xff0…...

编程日记 2025/5/28 7:39:32

一、下载 docker pull mysql:5.7 docker pull nacos/nacos-server:v2.2.2 docker images 二、mysql部署 1、创建目录存储数据信息 mkdir ~/mysql cd ~/mysql 2、运行 MySQL 容器 docker run -id \ -p 3306:3306 \ --name mysql \ -v $PWD/conf:/etc/mysql/conf.d \ -v $PWD/…...

编程日记 2025/5/25 10:28:00

10个非常基础的 Javascript 问题

Javascript是一种用于Web开发的编程语言。JavaScript在网络的客户端上运行。根据MDN，JavaScript（通常缩写为JS）是一种轻量级的，解释性的，面向对象的语言，具有一流的功能，并且最著名的是Web页面…...

编程日记 2025/5/24 1:08:11

SCP收容物221~225

注 ：此文接SCP收容物211~215,本文只供开玩笑 ,与steve_gqq_MC合作 --------------------------------------------------------------------------------------------------------------------------------- 目录 scp-221 scp-222 scp-223 scp-224 scp-225 s…...

编程日记 2025/5/27 7:01:03

基于迁移学习的ResNet50模型实现石榴病害数据集多分类图片预测

完整源码项目包获取→点击文章末尾名片！ 番石榴病害数据集背景描述番石榴 （Psidium guajava） 是南亚的主要作物，尤其是在孟加拉国。它富含维生素 C 和纤维，支持区域经济和营养。不幸的是，番石榴生产受到降…...

编程日记 2025/5/22 22:01:26

网络(三) 协议

目录 1. IP协议; 2. 以太网协议; 3. DNS协议, ICMP协议, NAT技术. 1. IP协议: 1.1 介绍: 网际互连协议, 网络层是进行数据真正传输的一层, 进行数据从一个主机传输到另一个主机. 网络层可以将数据主机进行传送, 那么传输层保证数据可靠性, 一起就是TCP/IP协议. 路径选择: 确…...

编程日记 2025/5/28 7:32:19

【mptcp】ubuntu18.04和MT7981搭建mptcp测试环境操作说明

目录安装ubuntu18.04，可以使用虚拟机安装... 2 点击安装VMware Tool 2 更新ubuntu18.04源... 4 安装ifconfig指令工具包... 5 安装vim工具包... 5...

编程日记 2025/5/22 22:00:17

递归的本质

字节面试题叠罗汉，很遗憾没想出来，看了答案挺巧妙的，但是居然是个案例题。。。复习一下递归的本质正面解决问题利用子问题来解决可以通过规约推导的，基本可以用递归解决！ 在写这道算法题时，我想规…...

编程日记 2025/5/28 2:11:25

如何使用tmux !

在tmux的界面按住shift，就可以和普通linux界面一样！！！！！！！！ 单击右键可以复制粘贴，滚动鼠标可以上下翻页！！！！…...

编程日记 2025/5/25 21:23:09

【Vim Masterclass 笔记25】S10L45：Vim 多窗口的常用操作方法及相关注意事项

文章目录 S10L45 Working with Multiple Windows1 水平分割窗口2 在水平分割的新窗口中显示其它文件内容3 垂直分割窗口4 窗口的关闭5 在同一窗口水平拆分出多个窗口6 关闭其余窗口7 让四个文件呈田字形排列8 光标在多窗口中的定位9 调节子窗口的尺寸大小10 变换子窗口的位置11…...

编程日记 2025/5/28 0:54:06

C语言练习（16）

猴子吃桃问题。猴子第一天摘下若干个桃子，当即吃了一半，还不过瘾，又多吃了一个。第二天早上又将剩下的桃子吃掉一半，又多吃了一个。以后每天早上都吃了前一天剩下的一半加一个。到第10天早上想再吃时，见只剩一个桃子了…...

编程日记 2025/5/27 10:34:33

【0x0012】HCI_Delete_Stored_Link_Key命令详解

目录一、命令参数二、命令格式及参数 2.1. HCI_Delete_Stored_Link_Key 命令格式 2.2. BD_ADDR 2.3. Delete_All 三、生成事件及参数 3.1. HCI_Command_Complete事件 3.2. Status 3.3. Num_Keys_Deleted 四、命令执行流程 4.1. 命令发送阶段 4.2. 控制器处理阶段…...

编程日记 2025/5/26 9:54:14

学习ASP.NET Core的身份认证（基于JwtBearer的身份认证10）

基于Cookie传递token的主要思路是通过用户身份验证后，将生成的token保存到Response.Cookies返回客户端，后续客户端访问服务接口时会自动携带Cookie到服务端以便验证身份。之前一直搞不清楚的是服务端程序如何从Cookie读取token进行认证（一般都…...

编程日记 2025/5/26 17:26:35

应用层协议 HTTP 讲解实战：从0实现HTTP 服务器

🌈 个人主页：Zfox_ 🔥 系列专栏：Linux 目录一：🔥 HTTP 协议 🦋 认识 URL🦋 urlencode 和 urldecode 二：🔥 HTTP 协议请求与响应格式 🦋 HTTP 请求…...

编程日记 2025/5/19 17:50:43

Linux权限管理：从用户切换到文件权限

在Linux系统中，权限管理是确保系统安全和资源合理分配的核心机制。它通过用户和用户组的管理、文件权限的设置以及特殊权限的使用，实现了对系统资源的精细控制。一、用户切换：su 和 sudo 1. 用户切换命令 su su（switch user&a…...

编程日记 2025/5/23 19:12:43

PyQt5超详细教程终篇

PyQt5超详细教程前言接： [【Python篇】PyQt5 超详细教程——由入门到精通（序篇）](【Python篇】PyQt5 超详细教程——由入门到精通（序篇）-CSDN博客) 建议把代码复制到pycahrm等IDE上面看实际效果，方便理…...

编程日记 2025/5/27 13:04:12

Alibaba Spring Cloud 四 Seata 的核心组件：TC

Seata 的 Transaction Coordinator (TC) 是分布式事务架构中的核心组件之一，它负责管理全局事务的生命周期，包括事务的创建、状态维护以及协调各分支事务的提交和回滚。以下是有关 TC 的详细解析及其配置和使用方法： 1. TC 的核心功能全局事…...

编程日记 2025/5/23 4:05:11

机器学习-线性回归（简单回归、多元回归）

这一篇文章，我们主要来理解一下，什么是线性回归中的简单回归和多元回归，顺便掌握一下特征向量的概念。一、简单回归简单回归是线性回归的一种最基本形式，它用于研究**一个自变量（输入）与一个因变量&…...

编程日记 2025/5/22 11:59:13

Java如何向http/https接口发出请求

用Java发送web请求所用到的包都在java.net下，在具体使用时可以用如下代码，你可以把它封装成一个工具类 import javax.net.ssl.*; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.Outpu…...

编程日记 2025/5/22 21:31:45

three.js+WebGL踩坑经验合集(1):THREE.Line无故消失的元凶

在项目开发过程中，笔者两次遇到同事的一个提问，我场景中的Line在相机旋转到某些角度或者移动到某些位置的时候会无故消失。由于业务场景复杂，所以这两位同事都是先花费了大量时间排查业务问题，然后才找我求助。这个问题抽象出来的…...

编程日记 2025/5/27 21:55:01

【ROS】RViz2源码分析（四）：初始化、启动

【ROS】郭老二博文之：ROS目录 1、简述 RViz2在main函数中，首先注册日志处理函数；将 RCLCPP_DEBUG 等日志记录函数，通过 rviz_common::set_logging_handlers() 注册到 rviz_common 中。然后，创建界面类 rviz_common::VisualizerApp，并执行初始化 vapp.init(argc, argv)…...

编程日记 2025/5/26 13:47:42

【MySQL】库的操作

欢迎拜访：雾里看山-CSDN博客本篇主题：【MySQL】库的操作发布时间：2025.1.23 隶属专栏：MySQL 目录库的创建语法使用编码规则认识编码集查看数据库默认的编码集和校验集查看数据库支持的编码集和校验集指定编码创建数据库验证不…...

编程日记 2025/5/24 17:27:39

豆包MarsCode 蛇年编程大作战 | 高效开发“蛇年运势预测系统”

🌟 嗨，我是LucianaiB！ 🌍 总有人间一两风，填我十万八千梦。 🚀 路漫漫其修远兮，吾将上下而求索。豆包MarsCode 蛇年编程大作战 | 🐍 蛇年运势预测在线体验地址：蛇年…...

编程日记 2025/5/28 6:56:57

新能源汽车充电桩选型以及安装应用

摘要:随着当前经济的不断发展,国家的科技也有了飞速的进步,传统的燃油汽车已经不能适应当前社会的发展,不仅对能源造成巨大的消耗,还对环境造成了污染,当前一种新型的交通运输工具正在占领汽车市场。在环境问题和能源问题愈发严重的当今社会,节能减排已经成为全世界的共同课题,…...

编程日记 2025/5/27 13:01:06

docker Ubuntu实战

目录 Ubuntu系统环境说明一、如何安装docker 二、发布.netcore应用到docker中三、查看docker信息 Ubuntu系统环境说明 cat /etc/os-release PRETTY_NAME"Ubuntu 22.04.5 LTS" NAME"Ubuntu" VERSION_ID"22.04" VERSION"22.04.5 LTS (…...

编程日记 2025/5/27 7:51:37

w-form-select.vue（自定义下拉框组件）(与后端字段直接相关性)

文章目录 1、w-form-select.vue 组件中每个属性的含义2、实例3、源代码 1、w-form-select.vue 组件中每个属性的含义好的，我们来详细解释 w-form-select.vue 组件中每个属性的含义，并用表格列出它们是否与后端字段直接相关： 属性解释表格&…...

编程日记 2025/5/27 5:50:20

深入探索 Nginx 的高级用法：解锁 Web 服务器的强大潜能

在当下互联网技术飞速发展的浪潮中，Nginx 凭借其轻量级、高性能的特性，在 Web 服务器和反向代理服务器领域脱颖而出，成为众多开发者和运维工程师的得力工具。它不仅能高效处理静态资源，在负载均衡、反向代理等方面也表现出色。然而…...

编程日记 2025/5/24 15:42:59

iOS开发设计模式篇第二篇MVVM设计模式

目录一、什么是MVVM 二、MVVM 的主要特点三、MVVM 的架构图四、MVVM 与其他模式的对比五、如何在iOS中实现MVVM 1.Model 2.ViewModel 3.View (ViewController) 4.双向绑定 5.文中完整的代码地址六、MVVM 的优缺点 1.优点 2.缺点七、MVVM 的应用场景八、结…...

编程日记 2025/5/28 1:55:42

kettle与Springboot的集成方法，完整支持大数据组件

目录概要整体架构流程技术名词解释技术细节小结概要在现代数据处理和ETL（提取、转换、加载）流程中，Kettle（Pentaho Data Integration, PDI）作为一种强大的开源ETL工具，被广泛应用于各种数据处理场景。…...

编程日记 2025/5/27 19:38:56

详解：TCP/IP五层（四层）协议模型

一.五层（四层）模型 1.概念 TCP/IP协议模型分为五层：物理层、数据链路层、网络层、传输层和应用层。这五层每一层都依赖于其下一层给它提供的网络去实现需求。 1）物理层：这是最基本的一层，也是最接近硬件…...

编程日记 2025/5/23 1:43:38

（七）Mapbox GL JS 表达式初识

以下是关于如何在 Mapbox GL JS 中使用表达式的详细讲解和代码示例。文章目录什么是 Mapbox GL JS 表达式？使用场景步骤1. 初始化地图2. 解释表达式总结什么是 Mapbox GL JS 表达式？ Mapbox GL JS 表达式是一种灵活的样式语言，允许你在 …...

编程日记 2025/5/26 10:38:34

阿里巴巴开发规范手册MySQL

1、MySQL 数据库 1.1、建表规约 1) 表达是与否概念的字段，必须使用 is_xxx 的方式命名，数据类型是 unsigned tinyint（1 表示是，0 表示否）。说明：任何字段如果为非负数，必须是 unsigned。注…...

编程日记 2025/5/25 8:12:09

SpringCloud微服务Gateway网关简单集成Sentinel

Sentinel是阿里巴巴开源的一款面向分布式服务架构的轻量级流量控制、熔断降级组件。Sentinel以流量为切入点，从流量控制、熔断降级、系统负载保护等多个维度来帮助保护服务的稳定性。官方文档：https://sentinelguard.io/zh-cn/docs/introduction.html …...

编程日记 2025/5/25 20:12:41

Linux下Ubuntun系统报错find_package(BLAS REQUIRED)找不到

Linux下Ubuntun系统报错find_package(BLAS REQUIRED)找不到这次在windows的WSL2中遇到了一个非常奇怪的错误，就是 CMake Error at /usr/share/cmake-3.22/Modules/FindPackageHandleStandardArgs.cmake:230 (message):Could NOT find BLAS (missing: BLAS_LIBRAR…...

编程日记 2025/5/26 2:34:01

私有IP、VLAN和VPC，分别适合哪些场景你知道吗？

当我们在云中构建应用程序，尤其是使用了第三方云服务商的服务并且我们无法完全掌控后端的每部分时，安全性可能是最需要关注的地方。但这是一项充满挑战的工作，因为保护应用程序的方法实在是太多了！为了改善安全性，开发…...

编程日记 2025/5/26 23:57:28

【学术会议论文投稿】深度解码：机器学习与深度学习的界限与交融

目录一、定义与起源：历史长河中的两条轨迹二、原理差异：从浅层到深层的跨越三、代码解析：实战中的机器学习与深度学习机器学习示例：线性回归深度学习示例：卷积神经网络(CNN) 四、应用差异：各自领…...

编程日记 2025/5/25 1:56:17

一位前端小白的2024总结

目录简要一、迷茫点的解决 （1）前端领域该怎么学？ （2）旧技术还需要学吗？ （3）我该学些什么？ 二、折磨点的解决 （1）学技术成果回报太慢怎么…...

编程日记 2025/5/24 5:30:23

状态模式——C++实现

目录 1. 状态模式简介 2. 代码示例 3. 单例状态对象 4. 状态模式与策略模式的辨析 1. 状态模式简介状态模式是一种行为型模式。状态模式的定义：状态模式允许对象在内部状态改变时改变它的行为，对象看起来好像修改了它的类。通俗的说就是一个对象…...

编程日记 2025/5/27 7:23:55

C# 控制打印机：从入门到实践

在开发一些涉及打印功能的应用程序时，使用 C# 控制打印机是一项很实用的技能。这篇文章就来详细介绍下如何在 C# 中实现对打印机的控制。一、准备工作安装相关库：在 C# 中操作打印机，我们可以借助System.Drawing.Printing命名空间&#x…...

编程日记 2025/5/27 4:17:10

【一个按钮一个LED】用STM32F030单片机实现苹果充电器的定时装置

文章目录前言一、要实现的功能1、循环定时2、倒计时3、指示灯提示4、使用场景二、实现方法1、使用方法2、电路设计三、程序代码和成品1.定时中断子程序2.键值处理3.主函数总结前言笔者前几年买苹果手机、IPAD配的适配器是A1443型号，这种5V1A，USB-A口、小功率的适配器，苹果…...

编程日记 2025/5/27 3:07:25

ansible自动化运维实战--script、unarchive和shell模块（6）

文章目录一、script模块1.1、功能1.2、常用参数1.3、举例二、unarchive模块2.1、功能2.2、常用参数2.3、举例三、shell模块3.1、功能3.2、常用参数3.3、举例一、script模块 1.1、功能 Ansible 的 script 模块允许你在远程主机上运行本地的脚本文件，其提供了一…...

编程日记 2025/5/22 22:36:16

LLM大模型实践18-评估（上）——存在一个简单的正确答案

准备数据 products_and_category { "电脑和笔记本": [ "TechPro 超极本", "BlueWave 游戏本", "PowerLite Convertible", "TechPro Desktop", "BlueWave Chromebook" ], "智能手机和配件": [ "…...

编程日记 2025/5/28 0:58:54

力扣-数组-704 二分查找

解析经典二分，重点在于左闭右闭区间约定好后，根据定义更新边界代码 class Solution { public:int search(vector<int>& nums, int target) {int left 0, right nums.size() - 1;while(left < right){int mid (left right) / 2;if(…...

编程日记 2025/5/24 16:21:01

K8S 快速实战

K8S 核心架构原理：我们已经知道了 K8S 的核心功能：自动化运维管理多个容器化程序。那么 K8S 怎么做到的呢？这里，我们从宏观架构上来学习 K8S 的设计思想。首先看下图： K8S 是属于主从设备模型（Master-Slave 架构），即有 Master 节点负责核心的调度、管理和运维，Slave…...

编程日记 2025/5/25 15:43:17

C#集合操作优化：高效实现批量添加与删除

在C#中，对集合进行批量操作（如批量添加或删除元素）通常涉及使用集合类型提供的方法和特性，以及可能的循环或LINQ查询来高效地处理大量数据。以下是一些常见的方法和技巧： 批量添加元素使用集合的AddRange方法&#x…...

编程日记 2025/5/27 0:27:18

Unity|小游戏复刻|见缝插针1(C#)

准备创建Scenes场景，Scripts脚本，Prefabs预制体文件夹修改背景颜色选中Main Camera 找到背景选择颜色，一种白中透黄的颜色创建小球将文件夹里的Circle拖入层级里选中Circle，位置为左右居中，偏上&…...

编程日记 2025/5/22 15:59:08

【Redis】持久化机制

目录前言： RDB 触发RDB持久化方法有俩种： 1.手动触发 2.自动触发 RDB文件的优缺点： AOF: AOF工作机制：编辑编辑重写机制： 前言： Redis是一个内存数据库，将数据存储在内存中&…...

编程日记 2025/5/26 10:48:53

AWScurl笔记

摘要 AWScurl是一款专为与AWS服务交互设计的命令行工具，它模拟了curl的功能并添加了AWS签名版本4的支持。这一特性使得用户能够安全有效地执行带有AWS签名的请求，极大地提升了与AWS服务交互时的安全性和有效性。 GitHub - okigan/awscurl: curl-like acc…...

编程日记 2025/5/27 7:13:50