【数据结构】堆(Heap)详解
在深入了解堆这一重要的数据结构之前,不妨先回顾一下我之前的作品 ——“二叉树详解”。
上篇文章👉剖析二叉树(Binary Tree)
二叉树作为一种基础的数据结构,为我们理解堆以及其他更复杂的数据结构奠定了坚实的基础。它的结构特点、遍历方式以及在不同场景下的应用,都与堆有着千丝万缕的联系。通过对二叉树的深入学习,能更好地帮助我们掌握堆的相关知识。
目录
一、引言
二、堆的基础概念
(一)完全二叉树与满二叉树
(二)堆的定义与性质
三、堆的操作
(一)堆的插入
(二)堆的删除
(三)最大堆
(四)最小堆
四、堆的应用
(一)堆排序
(二)优先队列
五、总结
一、引言
堆是计算机科学中一种非常重要的数据结构,它在众多算法和应用中发挥着关键作用。本文将深入探讨堆的相关概念、操作及其应用。
二、堆的基础概念
(一)完全二叉树与满二叉树
1.完全二叉树
- 若二叉树的深度为
,则除第
层外,其他层的结点全部达到最大值,且第
层的所有结点都集中在左子树。
2.满二叉树
- 满二叉树是一种特殊的完全二叉树,所有层的结点都是最大值。
(二)堆的定义与性质
1.堆的定义
- 堆(英语:heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。
个元素的序列
当且仅当满足下关系时,称之为堆:
堆分为大顶堆和小顶堆。在大顶堆中,父节点的值总是大于或等于子节点的值;在小顶堆中,父节点的值总是小于或等于子节点的值。
2.堆的性质
堆中某个节点的值总是不大于或不小于其父节点的值。
堆总是一棵完全二叉树。
将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。
注意:在二叉树中,若当前节点的下标为,则其父节点的下标为
,其左子节点的下标为
,其右子节点的下标为
。
三、堆的操作
(一)堆的插入
1.插入过程
- 每次插入都是将先将新数据放在数组最后。由于从这个新数据的父结点到根结点必然为一个有序的序列,现在的任务是将这个新数据插入到这个有序序列中,类似于直接插入排序中将一个数据并入到有序区间中。
- 例如,将数字
插入到堆中,堆的数组是
![]()
- 第一步是将新的元素插入到数组的尾部,数组变成,相应的树变成了:
107 25 1 16
- 此时堆属性不满足,因为
在的
上面(这是一个最大堆),需要交换和。得到:
107 165 1 2
- 现在还未完成,因为
也比
小。继续交换插入元素和它的父节点,直到父节点比它大或者到达树的顶部。这就是所谓的 shift-up,每一次插入操作后都需要进行,它将一个太大或者太小的数字 “浮起” 到树的顶部。
- 最后得到的堆:
167 105 1 2
- 插入操作的 C 语言代码示例
void insertHeap(int heap[], int *size, int value) {heap[*size] = value;int index = *size;//将孩子标为index(*size)++;while (index > 0) //将孩子调整到正确位置{int parentIndex = (index - 1) / 2;if (heap[index] > heap[parentIndex]) //如果孩子比父亲大,则交换{int temp = heap[index];heap[index] = heap[parentIndex];heap[parentIndex] = temp;index = parentIndex;//再次与其父亲比较直到break}else break;//孩子比父亲小则退出}
}
(二)堆的删除
1.删除过程
- 堆中每次都只能删除堆顶元素。为了便于重建堆,实际的操作是1.将最后一个数据的值赋给根结点,2.然后再从根结点开始进行一次从上向下的调整。3.调整时先在左右子结点中找最小的(对于最大堆),如果父结点比这个最小的子结点还小说明不需要调整了,反之将父结点和它交换后再考虑后面的结点。相当于根结点数据的 “下沉” 过程。
- 例如,删除树中的
:
167 105 1 2
- 顶部有一个空的节点,取出数组中的最后一个元素
,将它放到树的顶部。
- 然后进行 shift-down 操作。为了保持最大堆的堆属性,需要树的顶部是最大的数据。现在有两个数字
和
可用于交换,选择两者中的较大者
放在树的顶部,
交换和
,树变成了:
71 25
- 继续堆化直到该节点没有任何子节点或者它比两个子节点都要大为止。对于这个堆,只需要再有一次交换就恢复了堆属性:
75 2
- 删除操作的 C 语言代码示例
int deleteHeap(int heap[], int *size) {if (*size == 0) {return -1;}int value = heap[0];heap[0] = heap[*size - 1];(*size)--;int index = 0;while (1) {int leftChildIndex = 2 * index + 1;int rightChildIndex = 2 * index + 2;int largestIndex = index;if (leftChildIndex < *size && heap[leftChildIndex] > heap[largestIndex]) {largestIndex = leftChildIndex;}if (rightChildIndex < *size && heap[rightChildIndex] > heap[largestIndex]) {largestIndex = rightChildIndex;}if (largestIndex!= index) {int temp = heap[index];heap[index] = heap[largestIndex];heap[largestIndex] = temp;index = largestIndex;} else {break;}}return value;
}
(三)最大堆
1.构造最大堆
- 基本思想:首先将每个叶子节点视为一个堆,再将每个叶子节点与其父节点一起构造成一个包含更多节点的堆。所以,在构造堆的时候,首先需要找到最后一个节点的父节点,从这个节点开始构造最大堆;直到该节点前面所有分支节点都处理完毕,这样最大堆就构造完毕了。
- 假设树的节点个数为
,以
为下标开始编号,直到结束。对于节点
,其父节点为
;左孩子节点为
,右孩子节点为
。最后一个节点的下标为
,其父节点的下标为
。
- 例如,原始数据为
,采用顺序存储方式,对应的完全二叉树构建最大堆的过程如下:
- 首先,最后一个节点为
,其父节点为
,从
这个节点开始构造最大堆。
- 构造完毕之后,转移到下一个父节点
,直到所有父节点都构造完毕。
- 具体过程如下图所示(括号内为每次调整后的结果)
41 3 (3 1)2 16 9 10 (14 16 9 10)14 8 7 (2 8 7)(a) (b)41 10 (10 1)14 16 9 3 (14 16 9 3)2 8 7 (2 8 7)(c) (d)1614 108 7 9 32 4 1(e) 堆的初始化步骤
- 代码实现:
struct MaxHeap {Etype *heap; //数据元素存放的空间,下标从1开始存数数据,下标为0的作为工作空间,存储临时数据int HeapSize; //数据元素的个数int MaxSize; //存放数据元素空间的大小
};
MaxHeap H;void MaxHeapInit(MaxHeap &H) {for (int i = H.HeapSize / 2; i >= 1; i--) {H.heap[0] = H.heap[i];int son = i * 2;while (son <= H.HeapSize) {if (son < H.HeapSize && H.heap[son] < H.heap[son + 1])son++;if (H.heap[0] >= H.heap[son])break;else {H.heap[son / 2] = H.heap[son];son *= 2;}}H.heap[son / 2] = H.heap[0];}
}
2.最大堆插入节点
- 思想:先在堆的最后添加一个节点,然后沿着堆树上升。跟最大堆的初始化过程大致相同。
代码实现:
void MaxHeapInsert(MaxHeap &H, EType &x) {if (H.HeapSize == H.MaxSize)return false;int i = ++H.HeapSize;while (i!= 1 && x > H.heap[i / 2]) {H.heap[i] = H.heap[i / 2];i = i / 2;}H.heap[i] = x;return true;
}
3.最大堆堆顶节点删除
- 思想:将堆树的最后的节点提到根结点,然后删除最大值,然后再把新的根节点放到合适的位置。
代码实现:
void MaxHeapDelete(MaxHeap &H, EType &x) {if (H.HeapSize == 0)return false;x = H.heap[1];H.heap[0] = H.heap[H.HeapSize--];int i = 1, son = i * 2;while (son <= H.HeapSize) {if (son <= H.HeapSize && H.heap[0] < H.heap[son + 1])son++;if (H.heap[0] >= H.heap[son])break;H.heap[i] = H.heap[son];i = son;son = son * 2;}H.heap[i] = H.heap[0];return true;
}
(四)最小堆
整体操作和最大堆类似,主要区别在于比较大小的规则相反。在最小堆中,每个节点的值都不大于其子节点的值。插入和删除操作时,调整堆的方向也与最大堆相反,以保持最小堆的性质。
四、堆的应用
(一)堆排序
1.原理
堆排序利用了堆(通常是最大堆或最小堆)的特性来实现排序。对于最大堆,每次可以取出堆顶元素(即当前堆中的最大值),然后将堆的最后一个元素放到堆顶,再进行调整使堆保持最大堆性质。重复这个过程,就可以得到一个有序的序列。
2.示例
例如,对数组进行堆排序。首先根据该数组元素构建一个完全二叉树,具体过程如下(从左到右,从上到下按顺序一步一步的详细过程):
- 初始完全二叉树:
167320178
- 构建最大堆过程:
16 16 207 8 20 8 16 820 17 3 7
201787163
317 816 20173 87 16 2017 3 1616 8 16 8 3 87 3 7 20 716 3 87 8 7 8 7 33 20 163 7 37 8 3 9 81 17 20 16 16
-
然后进行堆排序,每次取出堆顶元素(最大值),与数组末尾元素交换,再对剩余元素进行调整,重复这个过程,最终得到有序数组。
-
相关参考文章:我的十大经典排序算法 (C++、Java 实现) 动图演示及代码解析 - 冒泡排序、选择排序、插入排序、快速排序、堆排序、希尔排序、归并排序、计数排序、桶排序、基数排序
有各个经典排序算法的动图介绍和源码,可以参考。
(二)优先队列
堆可以用于实现优先队列。在优先队列中,元素按照优先级进行排序。最大堆可以用于实现最大优先队列,每次取出的元素是优先级最高(值最大)的元素;最小堆可以用于实现最小优先队列,每次取出的元素是优先级最高(值最小)的元素。插入和删除元素时,堆的操作可以保证优先队列的性质始终满足。
五、总结
堆是一种非常重要的数据结构,具有独特的性质和高效的操作。它在堆排序、优先队列等算法和应用中有着广泛的应用。通过对堆的深入理解和掌握,我们可以更好地设计和实现高效的算法,解决各种实际问题。在未来的计算机科学领域,堆的应用可能会随着技术的发展而更加广泛,例如在大数据处理、实时系统等方面发挥更大的作用。同时,对于堆的研究和优化也将不断深入,以提高其性能和适用性。希望大家在学习堆的过程中,能充分体会到它的魅力和价值。
如果在阅读过程中有任何疑问或建议,欢迎随时交流。
💝💝💝感谢你看到最后,点个赞再走吧!💝💝💝
以下是一个投票,欢迎你参与:
相关文章:
【数据结构】堆(Heap)详解
在深入了解堆这一重要的数据结构之前,不妨先回顾一下我之前的作品 ——“二叉树详解”。 上篇文章👉剖析二叉树(Binary Tree) 二叉树作为一种基础的数据结构,为我们理解堆以及其他更复杂的数据结构奠定了坚实的基础。它…...

《Linux从小白到高手》理论篇(四):Linux用户和组相关的命令
List item 本篇介绍Linux用户和组相关的命令,看完本文,有关Linux用户和组相关的常用命令你就掌握了99%了。Linux用户和组相关的命令可以分为以下六类: 一.用户和用户组相关查询操作命令: Id id命令用于显示用户的身份标识。常见…...
OpenGL ES 之EGL(6)
OpenGL ES 之EGL(6) 简述 EGL是OpenGL ES的封装,目的是跨设备跨平台,隔离不同平台对窗口不同的实现。上一节我们基本没有使用到EGL,因为GLSurfaceView帮助我们处理了相关的逻辑,我们这一节来看一下EGL的一些概念以及接口的使用。…...

kotlin 委托
一、类委托 interface DB{fun insert() } class SqliteDB : DB {override fun insert() {println(" SqliteDB insert")} }class MySql : DB{override fun insert() {println(" MySql insert")} }class OracleDB : DB{override fun insert() {println(&quo…...

Stream流的中间方法
一.Stream流的中间方法 注意1:中间方法,返回新的Stream流,原来的Stream流只能使用一次,建议使用链式编程 注意2:修改Stream流中的数据,不会影响原来集合或者数组中的数据 二.filter filter的主要用法是…...

【车载开发系列】ParaSoft单元测试环境配置(四)
【车载开发系列】ParaSoft单元测试环境配置(四) 【车载开发系列】ParaSoft单元测试环境配置(四) 【车载开发系列】ParaSoft单元测试环境配置(四)一. 如何设置过滤二. 如何设置静态扫描的规则三. 如何设置单…...

IDEA 设置自动定位文件
一、场景分析 IDEA 在使用的过程中,发现有时候,打开一个类,它并不能自动帮我们在左侧 Project 树中定位出文件,需要自己手动点击 瞄准 图标。很不方便。 二、解决方法 1、点击 瞄准 图标旁边的 竖三点 2、将 Alwasy Select Opene…...

Nature Machine Intelligence 基于强化学习的扑翼无人机机翼应变飞行控制
尽管无人机技术发展迅速,但复制生物飞行的动态控制和风力感应能力,仍然遥不可及。生物学研究表明,昆虫翅膀上有机械感受器,即钟形感受器campaniform sensilla,探测飞行敏捷性至关重要的复杂气动载荷。 近日࿰…...
[Web安全 网络安全]-XXE 外部实体注入攻击XML
文章目录: 一:前言 1.定义 1.1 XXE 1.2 XML可扩展标记语言 2.DDT文档类型定义 2.1 分类 2.2 元素element DTD元素 DTD属性 2.3 实体entity DTD实体类别 DTD实体声明引用 声明:内部 外部 参数实体 公共实体 引用:…...

8--苍穹外卖-SpringBoot项目中套餐管理 详解(二)
目录 删除套餐 需求分析和设计 代码开发 根据id查询套餐 mapper层 Service层 ServiceImpl层 Mapper层 批量删除套餐 mapper层 Service层 ServiceImpl层 Mapper层 SetmealMapper.xml 修改套餐 需求分析和设计 代码开发 起售停售套餐 需求分析和设计 代码开发…...
测试面试题:pytest断言时,数据是符点类型,如何断言?
在使用 Pytest 进行断言时,如果数据是浮点类型,可以使用以下方法进行断言: 一、使用pytest.approx pytest.approx可以用来比较两个浮点数是否近似相等。例如: import pytestdef test_float_assertion():result 3.14159expecte…...
Python与MongoDB交互
一、基本概念 MongoDB: 一个面向文档的数据库系统,使用BSON(Binary JSON)作为存储格式。集合(Collection): 类似于关系型数据库中的表,是文档的集合。文档(Document): MongoDB中的基…...

安卓AI虚拟女友项目开发的Android开发环境搭建
第五章:Android开发环境搭建与基础入门 5-1 项目讲解思路说明 本文是安卓AI数字虚拟人项目实战的第五章,开发安卓AI安卓版数字虚拟人的Android基础部分。 在本章中,我们将详细介绍如何搭建Android开发环境,包括Android Studio的…...

基于SpringBoot+Vue+MySQL的智能垃圾分类系统
系统展示 用户前台界面 管理员后台界面 系统背景 随着城市化进程的加速,垃圾问题日益凸显,不仅对环境造成污染,也给城市管理带来了巨大挑战。传统的垃圾分类方式不仅费时费力,而且手工操作容易出现错误,导致垃圾分类效…...
你的个人文件管理助手:AI驱动的本地文件整理工具
🌐 引言 在数字化时代,我们经常面临文件管理的挑战。电脑中的文件杂乱无章,寻找特定文件变得既费时又费力。幸运的是,现在有了一款名为本地文件整理器的神器,它利用AI技术帮助你快速、智能地整理文件,同时…...

【PyTorch】环境配置
框架介绍 Pytorch简介 2017年1月,FAIR(Facebook AI Research)发布了PyTorch。PyTorch是在Torch基础上用python语言重新打造的一款深度学习框架。Torch是采用Lua语言作为接口的机器学习框架,但因为Lua语言较为小众,导…...
枫叶MTS格式转换器- 强大、操作简单的MTS、M2TS视频转换工具供大家学习研究参考
一款功能强大、操作简单的MTS、M2TS视频转换工具,欢迎下载使用。 使用本MTS格式转换器可以帮助您将索尼和松下等摄像机录制的MTS、M2TS格式高清视频转换为其他流行的视频格式,如MP4、3GP、AVI、MPEG、WMV、ASF、MOV、RM、VCD、SVCD、DVD、MKV、FLV、SWF、MPG、MP3、WAV、WMA…...
Vscode把全部‘def‘都收起来的快捷键
在 VSCode 中,你可以使用以下快捷键来收起所有函数定义 (def): Windows/Linux: Ctrl K, Ctrl 0macOS: Cmd K, Cmd 0 这个快捷键组合会折叠当前文件中所有的代码块(包括所有函数和类定义)。你可以通过相同的快捷键再次展开这…...

Web和UE5像素流送、通信教程
一、web端配置 首先打开Github地址:https://github.com/EpicGamesExt/PixelStreamingInfrastructure 找到自己虚幻引擎对应版本的项目并下载下来,我这里用的是5.3。 打开项目找到PixelStreamingInfrastructure-master > Frontend > implementat…...

【YOLO目标检测电梯间电动车与人数据集】共4321张、已标注txt格式、有训练好的yolov5的模型
目录 说明图片示例 说明 数据集格式:YOLO格式 图片数量:4321 标注数量(txt文件个数):4321 标注类别数:2 标注类别名称:person、electricBicycle 数据集下载:电梯间电动车与人数据集 图片示例 数据…...

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合
强化学习(Reinforcement Learning, RL)是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程,然后使用强化学习的Actor-Critic机制(中文译作“知行互动”机制),逐步迭代求解…...
逻辑回归:给不确定性划界的分类大师
想象你是一名医生。面对患者的检查报告(肿瘤大小、血液指标),你需要做出一个**决定性判断**:恶性还是良性?这种“非黑即白”的抉择,正是**逻辑回归(Logistic Regression)** 的战场&a…...

全球首个30米分辨率湿地数据集(2000—2022)
数据简介 今天我们分享的数据是全球30米分辨率湿地数据集,包含8种湿地亚类,该数据以0.5X0.5的瓦片存储,我们整理了所有属于中国的瓦片名称与其对应省份,方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...

12.找到字符串中所有字母异位词
🧠 题目解析 题目描述: 给定两个字符串 s 和 p,找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义: 若两个字符串包含的字符种类和出现次数完全相同,顺序无所谓,则互为…...
今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存
文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...
Xen Server服务器释放磁盘空间
disk.sh #!/bin/bashcd /run/sr-mount/e54f0646-ae11-0457-b64f-eba4673b824c # 全部虚拟机物理磁盘文件存储 a$(ls -l | awk {print $NF} | cut -d. -f1) # 使用中的虚拟机物理磁盘文件 b$(xe vm-disk-list --multiple | grep uuid | awk {print $NF})printf "%s\n"…...

GruntJS-前端自动化任务运行器从入门到实战
Grunt 完全指南:从入门到实战 一、Grunt 是什么? Grunt是一个基于 Node.js 的前端自动化任务运行器,主要用于自动化执行项目开发中重复性高的任务,例如文件压缩、代码编译、语法检查、单元测试、文件合并等。通过配置简洁的任务…...

《信号与系统》第 6 章 信号与系统的时域和频域特性
目录 6.0 引言 6.1 傅里叶变换的模和相位表示 6.2 线性时不变系统频率响应的模和相位表示 6.2.1 线性与非线性相位 6.2.2 群时延 6.2.3 对数模和相位图 6.3 理想频率选择性滤波器的时域特性 6.4 非理想滤波器的时域和频域特性讨论 6.5 一阶与二阶连续时间系统 6.5.1 …...
Java并发编程实战 Day 11:并发设计模式
【Java并发编程实战 Day 11】并发设计模式 开篇 这是"Java并发编程实战"系列的第11天,今天我们聚焦于并发设计模式。并发设计模式是解决多线程环境下常见问题的经典解决方案,它们不仅提供了优雅的设计思路,还能显著提升系统的性能…...
【大厂机试题解法笔记】矩阵匹配
题目 从一个 N * M(N ≤ M)的矩阵中选出 N 个数,任意两个数字不能在同一行或同一列,求选出来的 N 个数中第 K 大的数字的最小值是多少。 输入描述 输入矩阵要求:1 ≤ K ≤ N ≤ M ≤ 150 输入格式 N M K N*M矩阵 输…...