【初阶数据结构】树——二叉树——堆（中）

文章目录

前言

一、堆的概念与结构

二、堆的实现

堆的定义

1.初始化堆

2.堆的销毁

3.堆的插入

3.1向上调整算法

4.堆的判空

5.求有效个数

6.删除堆顶数据

6.1向下调整算法

7.获取栈顶数据

三、完整源码

总结

前言

上篇了解树和二叉树相关的概念，这篇学习一种特殊的二叉树--堆，通过认识堆来实现堆和堆的应用。

一、堆的概念与结构

如果有一个关键码的集合 K = { k0 , k1 , k2 , ...， k n−1 } ，把它的所有元素按完全二叉树的顺序存储方式存储，在一个一维数组中，并满足： K i <= K2∗ i+1 （ K i >= K2∗ i+1 且 K i <= K2∗ i+2 ）， i = 0、1、2... ，则称为小堆(或大堆)。将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆。
小根堆：

大根堆：

堆的特点：

  1. 堆中某个结点的值总是不大于或不小于其父结点的值；
  2. 堆总是一棵完全二叉树。

从二叉树的性质讨论出：

对于具有 n 个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有结点从
0 开始编号，则对于序号为 i 的结点有：
1. 若 i>0 ， i 位置结点的双亲序号： (i-1)/2 ； i=0 ， i 为根结点编号，无双亲结点
2. 若 2i+1<n ，左孩子序号： 2i+1 ， 2i+1>=n 否则无左孩子
3. 若 2i+2<n ，右孩子序号： 2i+2 ， 2i+2>=n 否则无右孩子

二、堆的实现

堆的定义

由此，我们可知堆的底层是数组来实现的，则堆的结构是顺序结构，可写出堆的结构定义

typedef int HPDatatype;
//堆的结构
typedef struct Heap
{HPDatatype* arr;int size;      //有效数据个数int capacity; //容量
}HP;

1.初始化堆

代码解析：

先对未开辟空间的数组指针置为空，再对有效个数和容量大小都置为0.

//初始化
void HPIint(HP* php)
{assert(php);php->arr = NULL;php->size = php->capacity = 0;
}

2.堆的销毁

代码解析：

先判断堆是否为空，不为空先对数组进行释放再置为NULL，再对有效个数和容量大小都置为0

注：对堆开辟空间使用完后就要对堆进行销毁，避免造成空间浪费，因此要对堆进行销毁

//销毁
void HPDesTroy(HP* php)
{//判断堆是否为空，不为空就直接free再置空assert(php);if (php->arr)free(php->arr);php->arr = NULL;php->size = php->capacity = 0;
}

3.堆的插入

代码解析：

堆的插入就是在尾部进行数据插入。先判断堆是否已满，堆已满就进行 realloc 增容并更新capacity。增容后，把插入进来的数据进行重新调整，用 AdjustUp 函数对堆进行调整

//往堆中插入数据(以建小堆为例)
void HPPush(HP* php, HPDatatype x)
{assert(php);if (php->size == php->capacity){//增容int newCapacity = php->capacity == 0 ? 4 : 2 * php->capacity;HPDatatype* tmp = (HPDatatype*)realloc(php->arr, sizeof(HPDatatype) * newCapacity);if (tmp == NULL){perror("realloc fail!\n");exit(1);}php->arr = tmp;php->capacity = newCapacity;}//插入数据php->arr[php->size] = x;//插入数据后用向上调整方法来调整成小堆或者大堆AdjustUp(php->arr, php->size);++php->size;
}

3.1向上调整算法

接下来给大家介绍AdjustUp 函数 

代码解析：

先将元素插入到堆的末尾,即最后一个孩子之后
插入之后如果堆的性质遭到破坏，将新插入结点顺着其双双亲往上调整到合适位置即可

由二叉树的性质，我们可知已知孩子结点可求父结点：Parent =(child-1)/2。在这里我们建小堆，要求孩子结点大于父结点，如果不满足就对进行交换，在让child 走到parent ，parent 走到parent 的父结点；如果满足不用交换直接跳出循环。

//向上调整算法：
void AdjustUp(HPDatatype* arr, int child)
{//已知子节点下标，来求父节点下标int parent = (child - 1) / 2;while (child>0){if (arr[child] > arr[parent])//建大堆就大于{Swap(&arr[child], &arr[parent]);//交换后，子节点会跑到旧位置的父节点，则再求新位置的父节点child = parent;parent = (child - 1) / 2;}else {break;//如果子节点大于父节点，则不需要变化直接跳出循环}}
}

时间复杂度：

因为堆是完全⼆叉树，⽽满⼆叉树也是完全⼆叉树，此处为了简化使⽤满⼆叉树来证明(时间复杂度本来看的就是近似值，多⼏个结点不影响最终结果)
分析：
第1层， 2 0 个结点，需要向上移动0层

第2层， 2 1 个结点，需要向上移动1层
第3层， 2 2 个结点，需要向上移动2层
第4层， 2 3 个结点，需要向上移动3层
......
第h层， 2 h −1 个结点，需要向上移动h-1层
则需要移动结点总的移动步数为：每层结点个数 * 向上调整次数（第⼀层调整次数为0）

4.堆的判空

代码解析：用bool函数来判断堆是否为空

bool HPEmpty(HP* php)
{assert(php);return php->size == 0;
}

5.求有效个数

代码解析：直接返回有效个数即可

int HPSize(HP* php)
{assert(php);return php->size;
}

6.删除堆顶数据

代码解析：

先判断堆是否为空堆，是就返回0，不是返回有效数据；让根结点和最后一个元素进行交换，把交换后的最后一个元素删除后，再进行向下调整算法

//删除堆顶数据(以建小堆为例)
void HPPop(HP* php)
{assert(!HPEmpty(php));//交换根节点和最后一个节点，再对新的最后一个节点进行删除Swap(&php->arr[0], &php->arr[php->size - 1]);--php->size;//使用向下调整算法AdjustDown(php->arr, 0, php->size);}

6.1向下调整算法

代码解析：

将堆顶元素与堆中最后一个元素进行交换
删除堆中最后一个元素
将堆顶元素向下调整到满足堆特性为止

由二叉树的性质，我们可知，已知parent 结点的下标，就可求左，右孩子结点的下标，左下标：2(parent )+1=child, 右下标：2parent +2=child 。把最后一个元素删除后，这里需要建小堆，先找到孩子结点中较小的结点，把父结点和较小的孩子结点进行交换，再让父结点走到较小的孩子结点的交换前的位置，再更新孩子结点的下标；如果父结点小于孩子结点就不用交换，直接跳出循环。

//向下调整算法
void AdjustDown(HPDatatype* arr, int parent, int n)
{//已知父节点，求子节点又可求左右子节点int child = parent * 2 + 1;//左子节点while (child<n){//找到最小的节点，让其与父节点进行交换，谁小谁往上调(如果是大堆，谁大谁往上调)if (child + 1 <n && arr[child] > arr[child + 1]){child++;}if (arr[child] < arr[parent]){Swap(&arr[child], &arr[parent]);//父节点走到旧的字节点下标，再求新子节点下标parent = child;child = parent * 2 + 1;}else {break;}}
}

时间复杂度：

第1层， 2 0 个结点，需要向下移动h-1层
第2层， 2 1 个结点，需要向下移动h-2层
第3层， 2 2 个结点，需要向下移动h-3层
第4层， 2 3 个结点，需要向下移动h-4层
......
第h-1层， 2 h −2 个结点，需要向下移动1层

则需要移动结点总的移动步数为：每层结点个数 * 向下调整次数

注：堆的向上调整算法和向下调整算法都可以建大堆和小堆。向上调整算法主要用于堆插入，向下调整算法主要用于堆应用和堆排序。通过两者得出的时间复杂度，可知向下调整算法时间复杂度比向上调整算法复杂度好。

7.获取栈顶数据

代码解析：直接返回栈顶的数据

HPDatatype HPTop(HP* php)
{assert(!HPEmpty(php));return php->arr[0];
}

三、完整源码

Heap,h：

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>//一、用顺序结构实现完全二叉树，底层是数组
typedef int HPDatatype;
//堆的结构
typedef struct Heap
{HPDatatype* arr;int size;      //有效数据个数int capacity; //容量
}HP;//初始化
void HPIint(HP* php);
//销毁
void HPDesTroy(HP* php);
//往堆中插入数据
void HPPush(HP* php, HPDatatype x);
//删除堆顶数据
void HPPop(HP* php);
//判空
bool HPEmpty(HP* php);
//求size
int HPSize(HP* php);
//获取栈顶数据
HPDatatype HPTop(HP* php);//向上调整算法：
void AdjustUp(HPDatatype* arr, int child);
//向下调整算法
void AdjustDown(HPDatatype* arr, int parent, int n);

Heap,c：

#include"Heap.h"//初始化
void HPIint(HP* php)
{assert(php);php->arr = NULL;php->size = php->capacity = 0;
}
//销毁
void HPDesTroy(HP* php)
{assert(php);//判断堆是否为空，不为空就直接free再置空if (php->arr)free(php->arr);php->arr = NULL;php->size = php->capacity = 0;
}//交换：父节点与子节点比较，谁小谁往上调(谁大谁往上调)
void Swap(int* x, int* y)
{int temp = *x;*x = *y;*y = temp;
}//向上调整算法：
void AdjustUp(HPDatatype* arr, int child)
{//已知子节点下标，来求父节点下标int parent = (child - 1) / 2;while (child>0){if (arr[child] > arr[parent])//建大堆就大于{Swap(&arr[child], &arr[parent]);//交换后，子节点会跑到旧位置的父节点，则再求新位置的父节点child = parent;parent = (child - 1) / 2;}else {break;//如果子节点大于父节点，则不需要变化直接跳出循环}}
}//往堆中插入数据(以建小堆为例)
void HPPush(HP* php, HPDatatype x)
{assert(php);if (php->size == php->capacity){//增容int newCapacity = php->capacity == 0 ? 4 : 2 * php->capacity;HPDatatype* tmp = (HPDatatype*)realloc(php->arr, sizeof(HPDatatype) * newCapacity);if (tmp == NULL){perror("realloc fail!\n");exit(1);}php->arr = tmp;php->capacity = newCapacity;}//插入数据php->arr[php->size] = x;//插入数据后用向上调整方法来调整成小堆或者大堆AdjustUp(php->arr, php->size);++php->size;
}///
//对堆进行判断是否为空
bool HPEmpty(HP* php)
{assert(php);return php->size == 0;
}
//求size
int HPSize(HP* php)
{assert(php);return php->size;
}//向下调整算法
void AdjustDown(HPDatatype* arr, int parent, int n)
{//已知父节点，求子节点又可求左右子节点int child = parent * 2 + 1;//左子节点while (child<n){//找到最小的节点，让其与父节点进行交换，谁小谁往上调(如果是大堆，谁大谁往上调)if (child + 1 <n && arr[child] > arr[child + 1]){child++;}if (arr[child] < arr[parent]){Swap(&arr[child], &arr[parent]);//父节点走到旧的字节点下标，再求新子节点下标parent = child;child = parent * 2 + 1;}else {break;}}
}//删除堆顶数据(以建小堆为例)
void HPPop(HP* php)
{assert(!HPEmpty(php));//交换根节点和最后一个节点，再对新的最后一个节点进行删除Swap(&php->arr[0], &php->arr[php->size - 1]);--php->size;//使用向下调整算法AdjustDown(php->arr, 0, php->size);}//获取栈顶数据
HPDatatype HPTop(HP* php)
{assert(!HPEmpty(php));return php->arr[0];
}

test,c：

#include"Heap.h"void test()
{HP hp;HPIint(&hp);HPPush(&hp, 6);HPPush(&hp, 4);HPPush(&hp, 8);HPPush(&hp, 10);//HPPop(&hp);//HPPop(&hp);//HPPop(&hp);//HPPop(&hp);while (!HPEmpty(&hp)){printf("%d ", HPTop(&hp));HPPop(&hp);//取栈顶就要删除栈顶，不然会一直循环}HPDesTroy(&hp);
}

总结

非常感谢大家阅读完这篇博客。希望这篇文章能够为您带来一些有价值的信息和启示。如果您发现有问题或者有建议，欢迎在评论区留言，我们一起交流学习。

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

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

相关文章

AM剪辑软件汉化版：简单易用，开启视频创作之旅

AM剪辑软件汉化版：简单易用，开启视频创作之旅

在短视频流量时代&#xff0c;视频剪辑已经成为许多人表达自我和记录生活的重要方式。无论是分享日常点滴、制作创意视频还是进行专业内容创作&#xff0c;一款功能强大且操作简便的视频剪辑软件是必不可少的。今天&#xff0c;我们要介绍的 AM剪辑软件汉化版&#xff0c;就是这…
阅读更多...
llfc项目分布式服务笔记

llfc项目分布式服务笔记

一、系统整体架构流程图（简明版） 复制代码 +---------------+ +------------------+ +----------------+ | 客户端 (Client) |--------->| GateServer |----------| StatusServer |<--+ +---------------+ +--------------…
阅读更多...
C++如何设计和实现缓存（cache）来减少对后端存储的访问压力

C++如何设计和实现缓存（cache）来减少对后端存储的访问压力

随着数据量的激增和用户对低延迟、高吞吐量需求的不断提升，如何减少系统瓶颈、提升响应速度成为了开发者的核心挑战之一。在这一背景下，缓存（cache）作为一种关键的技术手段，逐渐成为解决性能问题的核心策略。缓存的本质是通过存储频繁访问的数据或计算结果，减少对后端存储…
阅读更多...
华为设备端口隔离

华为设备端口隔离

端口隔离的理论与配置指南 一、端口隔离的理论 基本概念 端口隔离&#xff08;Port Isolation&#xff09;是一种在交换机上实现的安全功能&#xff0c;用于限制同一VLAN内指定端口间的二层通信。被隔离的端口之间无法直接通信&#xff0c;但可通过上行端口访问公共资源&#…
阅读更多...
1688平台商品详情接口开发指南（含Python代码示例）

1688平台商品详情接口开发指南（含Python代码示例）

接口概述 1688开放平台提供的商品详情接口&#xff08;item_get&#xff09;是获取商品核心数据的重要API&#xff0c;开发者可通过该接口获取商品标题、价格、规格参数、图片等详细信息。本文重点解析标题字段的获取方式&#xff0c;并提供完整代码示例。 接口请求参数 基础…
阅读更多...
Edge浏览器PDF字体显示错误

Edge浏览器PDF字体显示错误

Edge浏览器PDF字体显示错误 软件版本信息 Edge Version: 136.0.3240.50 Word Version: Microsoft Office 专业增强版2021问题描述 在Word中使用多级列表自动编号, 并使用Word软件自带的导出为PDF文件功能, 在Word中显示正常的数字, 在Edge中查看PDF将会出现渲染错误的现象,…
阅读更多...
Redis能保证数据不丢失吗之AOF

Redis能保证数据不丢失吗之AOF

我们都知道，Redis是一个基于内存的k-v数据库，既然是基于内存的，那么Redis如何保证数据不丢失？以及真的能做到数据的百分百不丢失吗？ 为什么Redis数据需要持久化机制？ Redis的一个常用场景是缓存，通常缓存丢失的话，我们也可以从数据库中重新找回，那么为什么Redis还需…
阅读更多...
Apache POI实现Excel的基本写入、导出操作

Apache POI实现Excel的基本写入、导出操作

目录 一、Apache POI 简介 二、入门案例(写入导出) 三、实际开发过程中的导出操作——&#xff08;将文件下载至客户端浏览器中&#xff09; 一、Apache POI 简介 Apache POI&#xff08;Poor Obfuscation Implementation&#xff09;是 Apache 软件基金会的开源项目&#…
阅读更多...
HTTP请求与前端资源未优化的系统性风险与高性能优化方案

HTTP请求与前端资源未优化的系统性风险与高性能优化方案

目录 前言一、未合并静态资源&#xff1a;HTTP请求的隐形杀手1.1 多文件拆分的代价1.2 合并策略与工具链实践 二、未启用GZIP压缩&#xff1a;传输流量的浪费2.1 文本资源的压缩潜力2.2 服务端配置与压缩算法选择 三、未配置浏览器缓存&#xff1a;重复请求的根源3.1 缓存失效的…
阅读更多...
AgentMesh开源多智能体 (Multi-Agent) 平台

AgentMesh开源多智能体 (Multi-Agent) 平台

AgentMesh 是一个开源的多智能体 (Multi-Agent) 平台&#xff0c;核心目标是解决多个智能体之间的通信和协同问题&#xff0c;真正实现 “11>2” 的效果。能够帮助用户快速创造自己的多智能体团队&#xff0c;或是让已有的多个单一智能体获得协同能力&#xff0c;最终解决更…
阅读更多...
基于Jetson Nano与PyTorch的无人机实时目标跟踪系统搭建指南

基于Jetson Nano与PyTorch的无人机实时目标跟踪系统搭建指南

引言&#xff1a;边缘计算赋能智能监控 在AIoT时代&#xff0c;将深度学习模型部署到嵌入式设备已成为行业刚需。本文将手把手指导读者在NVIDIA Jetson Nano&#xff08;4GB版本&#xff09;开发板上&#xff0c;构建基于YOLOv5SORT算法的实时目标跟踪系统&#xff0c;集成无人…
阅读更多...
从入门到登峰-嵌入式Tracker定位算法全景之旅 Part 8 ｜产品化与运维：批量标定、误差监控、OTA 升级与安全防护

从入门到登峰-嵌入式Tracker定位算法全景之旅 Part 8 ｜产品化与运维：批量标定、误差监控、OTA 升级与安全防护

Part 8 ｜产品化与运维：批量标定、误差监控、OTA 升级与安全防护 本章聚焦将嵌入式 Tracker 定位系统推向 量产与运维 阶段，覆盖 批量标定、误差监控、远程 OTA 升级 以及 定位安全防护，确保产品在大规模部署后仍能稳定、精准、可靠地运行。 一、批量标定平台搭建 标定流程…
阅读更多...
gsplat 渲染库 安装部署笔记

gsplat 渲染库 安装部署笔记

目录 Windows 安装 Nvdiffrast安装 gsplat安装成功笔记： cu118测试ok vs 编译安装报错： 安装命令： 报错结果： Windows 安装 pip install gsplat 安装成功，调用报错： python -c "from gsplat import csrc as _C" Traceback (most recent call last): …
阅读更多...
Java二维码学习

Java二维码学习

使用Java语言生成二维码有以下方式，一是谷歌的zxing，二是基于zxing实现的qrcode开源项目，三是基于zxing实现的qrgen开源项目 一 zxing 谷歌的zxing技术生成二维码，是MultiFormatWriter多写格式书写器生成BitMatrix位矩阵，然后将位矩阵的信息在BufferedImage中设置二维码…
阅读更多...
工业质检/缺陷检测领域最新顶会期刊论文收集整理 | AAAI 2025【持续更新中】

工业质检/缺陷检测领域最新顶会期刊论文收集整理 | AAAI 2025【持续更新中】

会议官方论文列表&#xff1a;https://ojs.aaai.org/index.php/AAAI/issue/view/624 其中&#xff0c;2025年是第三十九届AAAI人工智能大会&#xff0c;主要对第三十九届相关论文进行梳理&#xff0c;当前已初版28期(volume 39 no. 28) 【Attention】 虽然本文主要面向的领域…
阅读更多...
数据结构实验8.1：图的基本操作

数据结构实验8.1：图的基本操作

文章目录 一&#xff0c;实验目的二&#xff0c;实验内容三&#xff0c;实验要求四&#xff0c;算法分析五&#xff0c;示例代码8-1.cpp源码graph.h源码 六&#xff0c;操作步骤七&#xff0c;运行结果 一&#xff0c;实验目的 1&#xff0e;掌握图的邻接矩阵、邻接表的表示方…
阅读更多...
Spring Boot3 实现定时任务 每10分钟执行一次，同时要解决分布式的问题 区分不同场景

Spring Boot3 实现定时任务 每10分钟执行一次，同时要解决分布式的问题 区分不同场景

在Spring Boot 3中实现分布式定时任务&#xff0c;确保多实例环境下任务仅执行一次&#xff0c;可以采用以下方案&#xff1a; 方案一&#xff1a;Redis分布式锁&#xff08;推荐&#xff09; import org.springframework.data.redis.core.StringRedisTemplate; import org.sp…
阅读更多...
WPF MVVM入门系列教程（五、命令和用户输入）

WPF MVVM入门系列教程（五、命令和用户输入）

&#x1f9ed; WPF MVVM入门系列教程 一、MVVM模式介绍二、依赖属性三、数据绑定四、ViewModel五、命令和用户输入六、ViewModel案例演示 WPF中的命令模型 在WPF中&#xff0c;我们可以使用事件来响应鼠标和键盘动作。 但使用事件会具备一定的局限性&#xff0c;例如&#x…
阅读更多...
2025年01月09日德美医疗前端面试

2025年01月09日德美医疗前端面试

目录 vue2 的双向绑定的原理vue3 的双向绑定原理vue 的生命周期vue 子组件为何不能修改父组件的值js delete 删除数组的某一个值会怎么样vue 和 react 的 diff 算法什么是闭包原型链this指向 vue2 的双向绑定的原理 以下是 Vue 2 双向绑定的原理&#xff1a; 1. 核心概念 …
阅读更多...
知识图谱 + 大语言模型：打造更聪明、更可靠的AI大脑 —— 探索 GraphRAG 中文优化与可视化实践

知识图谱 + 大语言模型：打造更聪明、更可靠的AI大脑 —— 探索 GraphRAG 中文优化与可视化实践

大语言模型&#xff08;LLMs&#xff09;无疑是近年来人工智能领域最耀眼的明星。它们强大的自然语言理解和生成能力&#xff0c;在文本创作、代码生成、对话交互等众多领域展现了惊人的潜力。然而&#xff0c;当前的 LLMs 并非完美无缺&#xff0c;它们常常面临着“幻觉”&…
阅读更多...
最新文章

Copyright @ 2022~2023