【数据结构】二叉树之堆的实现

🔥博客主页:小王又困了
📚系列专栏:数据结构
🌟人之为学,不日近则日退
❤️感谢大家点赞👍收藏⭐评论✍️
目录
一、二叉树的顺序结构
📒1.1顺序存储
📒1.2堆的性质
📒1.3堆的分类
二、堆的实现
📒2.1堆的创建
📒2.2堆的初始化
📒2.3堆的插入
📒2.4向上调整数据
📒2.5堆的删除
📒2.6向下调整数据
📒2.7堆的销毁
🗒️前言:
在上一期的文章中我们学习了一些二叉树的知识,也了解了堆的概念。堆是一颗完全二叉树,分为大堆和小堆,今天我们将实现堆的各种功能。
一、二叉树的顺序结构
📒1.1顺序存储
顺序结构存储就是使用数组来存储,一般使用数组只适合表示完全二叉树,因为不是完全二叉树会有空间的浪费。而现实使用中只有堆才会使用数组来存储。二叉树顺序存储在物理上是一个数组,在逻辑上是一颗二叉树。

📒1.2堆的性质
- 堆中某个节点的之总是不大于或不小于其父亲节点的值
- 堆是一颗完全二叉树
📒1.3堆的分类
- 小堆:树中任意一个父亲都小于等于孩子
- 大堆:树中任意一个父亲都大于等于孩子
二、堆的实现
📒2.1堆的创建
堆的逻辑结构是树形结构,是我们想象出来的,实际上我们操作的数组,所以堆的创建和顺序表的结构相同。
typedef int HPDateType; typedef struct Heap {HPDateType* a;int size;int capacity; }HP;
📒2.2堆的初始化
我们有两种初始化的方式,一种是在初始化阶段不开辟空间,在插入过程中进行扩容;另一种是在初始化阶段就开辟空间。
void HeapInit(HP* php) {assert(php);php->a = NULL;php->size = 0;php->capacity = 0; }void HeapInit(HP* php) {assert(php); php->size = 0;php->capacity = 5;php->a = (HPDateType*)malloc(sizeof(HPDateType) * capacity);if (tmp == NULL){perror("malloc");exit(-1);} }
📒2.3堆的插入
堆是使用顺序结构的数组来存储的,我们使用尾插插入数据更方便,然后将数据调整到合适的位置。
void HeapPush(HP* php, HPDataType x) {assert(php);// 扩容if (php->size == php->capacity){int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newCapacity);if (tmp == NULL){perror("realloc fail");exit(-1);}php->a = tmp;php->capacity = newCapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1); }如图:在小堆中插入50,50比它的父亲小,所以要交换两数的位置。我们知道孩子的下标通过 parent=(child-1)/2 就可以得到父亲的下标,然后交换两数。
📒2.4向上调整数据
如果是小堆存储我们通过孩子的下标找到父亲,比较两数如果孩子小于父亲就交换,然后在向上比较,如果孩子不小于父亲就跳出循环。
void Swap(HPDataType* p1, HPDataType* p2) {HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp; }void AdjustUp(HPDataType* a, int child) {int parent = (child - 1) / 2;while (child > 0){if (a[child] < a[parent]){Swap(&a[child], &a[parent]);child = parent;parent = (parent - 1) / 2;}else{break;}} }
📒2.5堆的删除
我们使用挪动覆盖的方法删除根,会使关系混乱,剩下的值不一定是堆,而且效率很低。这里提供一种更好的方法,将根和最后一个值交换,然后删除,最后调整数据。
void HeapPop(HP* php) {assert(php);assert(php->size > 0);Swap(&php->a[0], &php->a[php->size - 1]);--php->size;AdjustDown(php->a, php->size, 0); }这里要注意有数据的时候才能删除,所以要加入 assert(php->size > 0) 进行判断。
📒2.6向下调整数据
如果是小堆存储我们要找到左右孩子中较小的数,然后与父亲交换,再找到下一层重复步骤,直到找到叶节点结束。
void AdjustDown(HPDataType* a, int n, int parent) {//默认左孩子是较小的int child = parent * 2 + 1;while (child < n){// 找出小的那个孩子if (child + 1 < n && a[child + 1] < a[child]){++child;}if (a[child] < a[parent]){Swap(&a[child], &a[parent]);// 继续往下调整parent = child;child = parent * 2 + 1;}else{break;}} }
📒2.7堆的销毁
我们使用动态开辟内存,要及时释放空间并置为空指针,不然会造成数据泄露。
void HeapDestroy(HP* php) {assert(php);free(php->a);php->a = NULL;php->size = php->capacity = 0; }
本次的内容到这里就结束啦。希望大家阅读完可以有所收获,同时也感谢各位读者三连支持。文章有问题可以在评论区留言,博主一定认真认真修改,以后写出更好的文章。你们的支持就是博主最大的动力。
相关文章:
【数据结构】二叉树之堆的实现
🔥博客主页:小王又困了 📚系列专栏:数据结构 🌟人之为学,不日近则日退 ❤️感谢大家点赞👍收藏⭐评论✍️ 目录 一、二叉树的顺序结构 📒1.1顺序存储 📒1.2堆的性质…...
电工-三极管输入输出特性曲线讲解
三极管特性曲线是反映三极管各电极电压和电流之间相互关系的曲线,是用来描述晶体三极管工作特性曲线,常用的特性曲线有输入特性曲线和输出特性曲线。这里以下图所示的共发射极电路来分析三极管的特性曲线。 输入特性曲线 该曲线表示当e极与c极之间的电…...
深入解析容器与虚拟化:技术、对比与生态
深入解析容器与虚拟化:技术、对比与生态 文章目录 深入解析容器与虚拟化:技术、对比与生态容器和虚拟化的基本概念和原理容器的定义和特点虚拟化的定义和特点 容器使用场景容器和虚拟机的对比虚拟化技术的四个特点容器实现虚拟化的原理常见容器引擎和容器…...
制作游戏demo的心得
制作这个游戏demo出来的心得 https://www.bilibili.com/video/BV1cF411m7Dh/ 制作游戏demo的心得 制作游戏demo,主要是为了表现自己的技术,那就一门心思想着如何提高表现力就行了,在整体的画面渲染风格方面或许没有什么可选择的,…...
Web Tour Server窗口闪现
1.打开该文件所在位置 2.右击选择编辑,在最后一行加上pause,保存后重新打开Server窗口 3.重新打开后,若出现以下情况: 以管理员身份打开cmd命令行,输入命令netstat -aon|findstr “1080”,查看1080端口占用…...
Linux下的基本指令
目录 01. ls 指令 02. pwd命令 03. cd 指令 04. touch指令 05.mkdir指令(重要): 06.rmdir指令 && rm 指令(重要): 07.man指令(重要): 08mv指令ÿ…...
随机数生成器代码HTML5
代码如下 <!DOCTYPE html> <html> <head> <title>随机数生成器</title> <meta name"viewport" content"widthdevice-width, initial-scale1.0"> <style> body { text-align: center; bac…...
正确理解redux Toolkits中createSlice的action.payload
使用redux Toolkits中的createSlice编写extraReducers经常看到使用action.payload来更新state状态值: 那么action.payload指的到底是什么? 让我们看看action的定义部分: 注意: action.payload不是上面ajax请求的返回内容&#x…...
YOLOv8快速复现 官网版本 ultralytics
YOLOV8环境安装教程.:https://www.bilibili.com/video/BV1dG4y1c7dH/ YOLOV8保姆级教学视频:https://www.bilibili.com/video/BV1qd4y1L7aX/ b站视频:https://www.bilibili.com/video/BV12p4y1c7UY/ 1 平台搭建YOLOv8 平台:https://www.a…...
Haproxy搭建 Web 群集实现负载均衡
目录 1 Haproxy 1.1 HAProxy的主要特性 1.2 HAProxy负载均衡策略 1.3 LVS、Nginx、HAproxy的区别 2 Haproxy搭建 Web 群集 2.1 haproxy 服务器部署 2.1.1 关闭防火墙 2.1.2 内核配置(实验环境可有可无) 2.1.3 安装 Haproxy 2.1.4 Haproxy服务…...
Tessy 5.0.4
Tessy 5.0.4 Linux 2692407267qq.com,更多内容请见http://user.qzone.qq.com/2692407267/...
mybatis-plus根据指定条件批量更新
1.service实现类中 比如我这里只针对UserEntity,在UserServiceImpl下(该实现类是继承了mybatis-plus的ServiceImpl的)新增如下代码: public boolean updateBatchByQueryWrapper(Collection<UserEntity> entityList, Funct…...
虹科方案 | LIN/CAN总线汽车零部件测试方案
文章目录 摘要一、汽车零部件测试的重要性?二、虹科的测试仿真工具如何在汽车零部件测试展露头角?三、应用场景**应用场景1:方向盘开关的功能测试****应用场景2:各类型电机的控制测试****应用场景3:RGB氛围灯的功能测试…...
[solidity]合约调用合约
先写一个简单的合约将其部署,部署后的合约地址为:0xd9145CCE52D386f254917e481eB44e9943F39138 // SPDX-License-Identifier: MIT pragma solidity ^0.8.0;contract A{string myname;function setName(string memory _name) public{myname_name;}functi…...
Vulnhub系列靶机---JANGOW 1.0.1
文章目录 网卡配置信息收集主机发现端口扫描 漏洞利用反弹Shell提权 靶机文档:JANGOW 1.0.1 下载地址:Download (Mirror) 难易程度:. 网卡配置 水果味儿 信息收集 主机发现 端口扫描 访问80端口 点击site目录 点击页面上方的一个选项&…...
肖sir__项目环境之全流程__005
一、测试流程(h模型) 1、需求文档(产品) 需求文档(软件需求规格说明书srs) (1)如何分析需求 a、显示需求(主流程、功能,业务) b、隐性需求&#x…...
搜狗输入法下键翻页
搜狗输入法下键翻页 从官网下载 搜狗输入法智慧版关闭超级候选关闭候选...
C#多线程
一、多线程实现方式 1. 使⽤Thread类: System.Threading.Thread 类是C#中最基本的多线程编程⼯具。 2. 使⽤ThreadPool: 线程池是⼀个管理和重⽤线程的机制,它可以在应⽤程序中创建和使 ⽤多个线程,⽽⽆需显式地管理线程的…...
Unity 编辑器常用方法
unity编辑器开发 脚本注解1. RuntimeInitializeOnLoadMethod2. ColorUsage3. Header4. SerializeField5. HideInInspector6. Space7. Range8. Multiline9.[RequireComponent(typeof())]10.HelpURL 右键菜单注解1. CreateAssetMenu - 针对ScriptableObject 菜单栏注解1. MenuIt…...
21 mysql ref 查询
前言 这里主要是 探究一下 explain $sql 中各个 type 诸如 const, ref, range, index, all 的查询的影响, 以及一个初步的效率的判断 这里会调试源码来看一下 各个类型的查询 需要 lookUp 的记录 以及 相关的差异 此系列文章建议从 mysql const 查询 开始看 测试表结构…...
智慧医疗能源事业线深度画像分析(上)
引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...
工业安全零事故的智能守护者:一体化AI智能安防平台
前言: 通过AI视觉技术,为船厂提供全面的安全监控解决方案,涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面,能够实现对应负责人反馈机制,并最终实现数据的统计报表。提升船厂…...
Java 8 Stream API 入门到实践详解
一、告别 for 循环! 传统痛点: Java 8 之前,集合操作离不开冗长的 for 循环和匿名类。例如,过滤列表中的偶数: List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...
Python爬虫实战:研究feedparser库相关技术
1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...
前端导出带有合并单元格的列表
// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...
376. Wiggle Subsequence
376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...
CocosCreator 之 JavaScript/TypeScript和Java的相互交互
引擎版本: 3.8.1 语言: JavaScript/TypeScript、C、Java 环境:Window 参考:Java原生反射机制 您好,我是鹤九日! 回顾 在上篇文章中:CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...
JVM——对象模型:JVM对象的内部机制和存在方式是怎样的?
引入 在Java的编程宇宙中,“Everything is object”是最核心的哲学纲领。当我们写下new Book()这样简单的代码时,JVM正在幕后构建一个复杂而精妙的“数据实体”——对象。这个看似普通的对象,实则是JVM内存管理、类型系统和多态机制的基石。…...
Kafka 消息模式实战:从简单队列到流处理(一)
一、Kafka 简介 ** Kafka 是一种分布式的、基于发布 / 订阅的消息系统,由 LinkedIn 公司开发,并于 2011 年开源,后来成为 Apache 基金会的顶级项目。它最初的设计目标是处理 LinkedIn 公司的海量数据,如用户活动跟踪、消息传递和…...
Polarctf2025夏季赛 web java ez_check
第一次自己做出一个java,值得小小的记录,polar的java真得非常友好 反编译jar包,一眼就看到有个/deserialize 路由,接受base64的序列化数据,base64解码后 经过一次kmp检查,再由SafeObjectInputStream来反序列…...



