堆和二叉树的动态实现（C语言实现）

请添加图片描述

✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅
✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨
🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿
🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟
🌟🌟 追风赶月莫停留 🌟🌟
🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀
🌟🌟 平芜尽处是春山🌟🌟
🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟
🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿
✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨
✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅

🍋堆和队二叉树

  • 🍑二叉树
    • 🍍二叉树的含义
    • 🍍二叉树的结构
    • 🍍二叉树的存储结构
  • 🍑堆
    • 🍍堆的含义
    • 🍍堆的结构
    • 🍍堆的实现
      • 🍌补充条件
      • 🍌堆的初始化
      • 🍌堆的销毁
      • 🍌堆的插入
      • 🍌 堆的删除
      • 🍌取堆顶的数据
      • 🍌堆的数据个数
      • 🍌堆的判空
      • 🍌堆的整体代码实现

🍑二叉树

🍍二叉树的含义

二叉树是一种树形结构，其特点是每个节点最多有两个子树。

二叉树是一种有序树，这意味着它的子树按照一定的顺序排列，通常左子树出现在右子树之前。二叉树的递归定义可以描述为：二叉树可以是空的，也可以由一个根节点和两个互不相交的子树组成，这两个子树分别称为左子树和右子树。左子树和右子树自身也构成二叉树。

🍍二叉树的结构

在这里插入图片描述

在这里插入图片描述
现实中的二叉树：
在这里插入图片描述

在这里插入图片描述

现实中的树，就是我们学过的二叉树倒过来的样子，大家可以把手机屏幕倒过来看试试。

🍍二叉树的存储结构

二叉树分为顺序存储和链式存储

在这里插入图片描述

顺序存储：类似于数组的存储形式，但只有完全二叉树才会用顺序存储，这样才不会造成空间的浪费

在这里插入图片描述

链式存储：利用了链表的性质。每个节点都存储了上个树和下个树的位置，这也就是带头指针的双链表结构

🍑堆

🍍堆的含义

堆是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：
（1）堆中某个结点的值总是不大于或不小于其父结点的值；
（2）堆总是一棵完全二叉树。
（3）将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆。常见的堆有 二叉堆、斐波那契堆等。
（4）堆的物理结构本质上是顺序存储的，是线性的。但在逻辑上不是线性的，是完全二叉树的这种逻辑储存结构。 堆的这个数据结构，里面的成员包括一维数组，数组的容量，数组元素的个数，有两个直接后继。

🍍堆的结构

在这里插入图片描述

堆的结构就是特殊的二叉树结构，也就是上图中完全二叉树的样子

🍍堆的实现

在这里插入图片描述

堆的实现又分为大堆和小堆
大堆：任何父节点都大于等于子节点。
小堆：任何父节点都小于等于子节点。
两个子节点之间的大小没有明确规定

🍌补充条件

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>

typedef int HPDatetype;
typedef struct Heap
{
	HPDatetype* a;
	int catacity;
	int size;
}HP;

void Swap(HPDatetype *a1, HPDatetype *a2)
{
	HPDatetype cur = *a1;
	*a1 = *a2;
	*a2 = cur;
}

Swap（）函数是交换两个数的作用，是利用结构体形式创建的堆

🍌堆的初始化

void HeapInia(HP* ps)
{
	assert(ps);//防止堆为空
	ps->a = NULL;
	ps->size = ps->catacity = 0;
}

🍌堆的销毁

void HeapDestroy(HP* ps)
{
	assert(ps);//防止堆为空
	free(ps->a);
	ps->a = NULL;
	ps->size = 0;
	ps->catacity = 0;
}

🍌堆的插入

void AdjustUp(HPDatetype* 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;
		}
	}
}

void HeapPush(HP* ps, HPDatetype x)
{
	assert(ps);//防止堆为空
	if (ps->catacity == ps->size)
	{
		if (ps->catacity == 0)
		{
			ps->catacity = 2;
		}
		else
		{
			ps->catacity *= 2;
		}
		int newcatacity = ps->catacity;

		HPDatetype* cur = (HPDatetype*)realloc(ps->a, sizeof(HPDatetype) * newcatacity);
		if (cur == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		ps->a = cur;
		ps->catacity = newcatacity;
	}
	ps->a[ps->size] = x;
	(ps->size)++;

	AdjustUp(ps->a, ps->size - 1);
}

AdjustUp（）函数是把子节点向上调整的作用，因为我们利用数组形式建立堆，只能分为大堆和小堆，所以需要重新设计一个函数来调整子节点的位置。在这里我们是创建小堆。关于怎么向上找父节点，是利用了数组的位置特性。数组是从0开始，大家就可以找规律，以父节点找子节点就是需要加1再除以2，以子节点找父节点就是减1除以2。

🍌 堆的删除

void AdjustLown(HPDatetype* a, int n, int parent)//向下调整
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && a[child] > a[child + 1])
		{
			child++;
		}

		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void HeapPop(HP* ps)
{
	assert(ps);
	assert(ps->size > 0);

	Swap(&(ps->a[0]), &(ps->a[ps->size - 1]));
	(ps->size)--;

	AdjustLown(ps->a, ps->size, 0);//向下调整

}

堆的删除，在这里我们是删除的堆顶数据。
首先我们是先把堆顶数据和堆尾数据交换，然后再删除堆顶数据，最后利用函数AdjustLown()进行向下调整就行。
如果是小堆，取出来的数据就是依次变大，相反是大堆，取出来的数据就是依次变小。
堆在这里还有一个应用，就是堆排序。小堆就是升序，大堆就是降序。

🍌取堆顶的数据

HPDatetype HeapTop(HP* ps)
{
	assert(ps);
	assert(ps->size > 0);

	return ps->a[0];
}

返回堆顶数据即可

🍌堆的数据个数

int HeapSize(HP* ps)
{
	return ps->size;
}

直接返回ps->size即可

🍌堆的判空

bool HeapEmpty(HP* ps)
{
	assert(ps);
	return ps->size == 0;
}

注意，这里判空用到bool需要头文件名#include<stdbool.h>

🍌堆的整体代码实现

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>

typedef int HPDatetype;
typedef struct Heap
{
	HPDatetype* a;
	int catacity;
	int size;
}HP;

void HeapInia(HP* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->catacity = ps->size = 0;
}

void HeapDestroy(HP* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->size = ps->catacity;
}

void Swap(HPDatetype* a1, HPDatetype* a2)
{
	HPDatetype cur = *a1;
	*a1 = *a2;
	*a2 = cur;
}

void AdjustUp(HPDatetype* 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;
		}
	}
}

void HeapPush(HP* ps, HPDatetype x)
{
	assert(ps);
	if (ps->size == ps->catacity)
	{
		if (ps->catacity == 0)
			ps->catacity = 2;
		else
			ps->catacity *= 2;
		int newcatacity = ps->catacity;
		HPDatetype* cur = (HPDatetype*)realloc(ps->a, sizeof(HPDatetype) * newcatacity);
		if (cur == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		ps->a = cur;
		ps->catacity = newcatacity;
	}
	ps->a[ps->size] = x;
	(ps->size)++;

	AdjustUp(ps->a, ps->size - 1);

}

void AdjustLown(HPDatetype* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && a[child] > a[child + 1])
		{
			child++;
		}

		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void HeapPop(HP* ps)
{
	assert(ps);
	assert(ps->size > 0);

	Swap(&(ps->a[0]), &(ps->a[ps->size - 1]));
	(ps->size)--;

	AdjustLown(ps->a, ps->size, 0);

}

HPDatetype HeapTop(HP* ps)
{
	assert(ps);
	assert(ps->size > 0);

	return ps->a[0];
}

int HeapSize(HP* ps)
{
	return ps->size;
}

bool HeapEmpty(HP* ps)
{
	assert(ps);
	return ps->size == 0;
}

void HeapPrint(HP *ps)
{
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}

int main()
{
	int a[] = { 65,100,70,32,50,60 };
	int size = sizeof(a) / sizeof(a[0]);
	HP ps;
	HeapInia(&ps);
	for (int i = 0; i < size; i++)
	{
		HeapPush(&ps, a[i]);
	}
	HeapPrint(&ps);

	int net = HeapSize(&ps);

	//堆排序
	while (!HeapEmpty(&ps))
	{
		printf("%d ", HeapTop(&ps));
		HeapPop(&ps);
	}
	
	printf("%d ", net);

	HeapDestroy(&ps);

	return 0;
}

上面我也不充了堆排序，大家有兴趣可以试试，由于我这里是建的小堆，所以排出来的序是升序。

有不足的地方欢迎大家指正,谢谢！！！

请添加图片描述

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/431069.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Linux - 基础IO

Linux - 基础IO

1、回顾 1.1、来段代码回顾C文件接口 hello.c写文件 #include <stdio.h> #include <string.h> int main() {FILE *fp fopen("myfile", "w");if(!fp){printf("fopen error!\n");}const char *msg "hello bit!\n";int …
阅读更多...
xss.haozi.me：0x03及04

xss.haozi.me：0x03及04

这里有一个正则所以&#xff08;&#xff09;要用到实体编码 <a href"javascript:alert1">cc</a> 03 04都一样
阅读更多...
在线客服系统部署ssl开启https无法自动获取提示消息解决办法

在线客服系统部署ssl开启https无法自动获取提示消息解决办法

▇ 增加https无法收发消息&#xff1a; 严格按照教程修改 1./站点目录/public目录下,修改index.php define(whost,wss://kf.tpym.cn); define(wport,443); 2./站点目录/service 目录下,修改config.php // websocket 端口&#xff0c;客服系统网页会连这个端口 $websocket_…
阅读更多...
防患未然，OceanBase巡检工具应用实践——《OceanBase诊断系列》之五

防患未然，OceanBase巡检工具应用实践——《OceanBase诊断系列》之五

1. OceanBase为什么要做巡检功能 尽管OceanBase拥有很好的MySQL兼容性&#xff0c;但在长期的生产环境中&#xff0c;部署不符合标准规范、硬件支持异常&#xff0c;或配置项错误等问题&#xff0c;这些短期不会出现的问题&#xff0c;仍会对数据库集群构成潜在的巨大风险。为…
阅读更多...
1999-2022年30省平均受教育年限（含原始数据和具体计算过程+计算结果）

1999-2022年30省平均受教育年限（含原始数据和具体计算过程+计算结果）

1999-2022年30省平均受教育年限&#xff08;含原始数据和具体计算过程&#xff09; 1、时间&#xff1a;1999-2022年 2、范围&#xff1a;30省&#xff08;剔除西藏&#xff09; 3、计算方式&#xff1a;平均受教育年限&#xff08;未上学人数*0小学人数*6初中人数*9高中人数…
阅读更多...
AI大模型的预训练、迁移和中间件编程

AI大模型的预训练、迁移和中间件编程

大家好&#xff0c;我是爱编程的喵喵。双985硕士毕业&#xff0c;现担任全栈工程师一职&#xff0c;热衷于将数据思维应用到工作与生活中。从事机器学习以及相关的前后端开发工作。曾在阿里云、科大讯飞、CCF等比赛获得多次Top名次。现为CSDN博客专家、人工智能领域优质创作者。…
阅读更多...
python.模块与包

python.模块与包

1.模块是什么 本质上是一种python文件&#xff0c;以.py结尾&#xff0c;里面有类&#xff0c;函数&#xff0c;变量等&#xff0c;认为这是一个工具包&#xff0c;每个模块有不同的功能&#xff0c;导入后可以直接使用 2.模块的导入 方法1 import 模块名 使用&#xff1a…
阅读更多...
展示模型展台的高度一般为多少---模大狮模型网

展示模型展台的高度一般为多少---模大狮模型网

展示模型展台的高度一般取决于多个因素&#xff0c;包括展示物品的大小、展台的设计风格、展览场地的限制等。一般来说&#xff0c;展示模型展台的高度可以根据以下几点考虑&#xff1a; 展示物品的大小&#xff1a;如果展示物品比较大或需要竖立展示&#xff0c;展台的高度可能…
阅读更多...
GraphGeo参文19：Auto-Encoding Variational Bayes

GraphGeo参文19：Auto-Encoding Variational Bayes

https://arxiv.org/abs/1312.6114 [19] Diederik P Kingma and Max Welling. 2014. Auto-encoding variational bayes. In ICLR. 【前言】：VAE模型是Kingma(也是Adam的作者)大神在2014年发表的文章，是一篇非常非常经典，且实现非常优雅的生成模型，同时它还为bayes概率图模型…
阅读更多...
LVS负载均衡集群——NAT地址转换模式与DR直接路由

LVS负载均衡集群——NAT地址转换模式与DR直接路由

目录 一、LVS集群基本介绍 1、集群是什么&#xff1f; 2、集群的类型 ①负载均衡集群 ②高可用群集 ③高性能运算群集 3、负载均衡集群的结构 第一层&#xff0c;负载调度器 第二层&#xff0c;服务器池 第三层&#xff0c;共享存储 4、LVS负载均衡集群的三种工作模…
阅读更多...
学习计算天数

学习计算天数

学习计算天数 题目描述&#xff1a;解法思路&#xff1a;解法代码&#xff1a;运行结果&#xff1a; 题目描述&#xff1a; 输入y和m两个整数&#xff0c;y表示年份&#xff0c;m表示月份&#xff0c;计算y年m月有多少天&#xff0c;并输出天数。 测试1&#xff1a; 输⼊&…
阅读更多...
Redis常见的15个【坑】，避坑指南

Redis常见的15个【坑】，避坑指南

一、常见命令 1.1 过期时间意外丢失 原因&#xff1a; SET命令如果不设置过期时间&#xff0c;那么Redis会自动【擦除】这个key的过期时间 1.2 DEL命令阻塞redis key是String类型时&#xff0c;DEL时间复杂度是O(1)key是List/Hash/Set/ZSet类型&#xff0c;DEL时间复杂度是…
阅读更多...
FRM模型十五：净值归因之Fama_French三因子模型

FRM模型十五：净值归因之Fama_French三因子模型

文章目录 一、起源二、构建因子三、投资组合的净值归因1. 市场因子2. 规模因子3.价值因子4. 基于净值的归因方法 三、代码实现 一、起源 在多因子模型推出之前&#xff0c;CAPM模型被视为资产定价的第一标准。随着市场不断发展&#xff0c;发现了越来越多CAPM模型无法解释的现…
阅读更多...
Microsoft@ppt@快速掌握核心功能@常用功能培训

Microsoft@ppt@快速掌握核心功能@常用功能培训

文章目录 refs动画动画的用途逐部分显示内容实现问答效果部分地修改页面内容动画效果 常用窗口对象选择窗口&#x1f47a;批量选择对象 如何为重叠的对象高效的命名重命名方式方案1方案2对象重命名原则重命名后如何使用tips 动画窗口&#x1f47a; 幻灯片管理幻灯片母版幻灯片母…
阅读更多...
【软件测试】一个扫码支付的二维码怎么测（测试点分析）

【软件测试】一个扫码支付的二维码怎么测（测试点分析）

目录&#xff1a;导读 前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结&#xff08;尾部小惊喜&#xff09; 前言 面试的时候&#…
阅读更多...
VS统计代码行数

VS统计代码行数

1.使用查找和替换方式 按CTRLSHIFTF (Find in files)&#xff0c;勾上支持正则表达式&#xff0c; 然后输入搜索内容&#xff1a;^:b*[^:b#/].*$ 如图所示&#xff1a; 2.查看查询结果 需要注意&#xff1a;#开头和/开头或者空行都不计入代码量。
阅读更多...
javascript操作DOM的方法

javascript操作DOM的方法

目录 1. 弹出框 2. 定时器 3. 导航与URL 4. 浏览器信息 5. 窗口控制 6. 屏幕信息 7. 历史对象 1. 弹出框 警告框&#xff08;Alert&#xff09; window.alert(这是一个警告消息); 确认框&#xff08;Confirm&#xff09; var isConfirmed window.confirm(您确定要执…
阅读更多...
【开源】SpringBoot框架开发用户画像活动推荐系统

【开源】SpringBoot框架开发用户画像活动推荐系统

目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 数据中心模块2.2 兴趣标签模块2.3 活动档案模块2.4 活动报名模块2.5 活动留言模块 三、系统设计3.1 用例设计3.2 业务流程设计3.3 数据流程设计3.4 E-R图设计 四、系统展示五、核心代码5.1 查询兴趣标签5.2 查询活动推荐…
阅读更多...
Java学习笔记002——类的修饰符

Java学习笔记002——类的修饰符

在Java语言中&#xff0c;类的访问修饰符决定了其它类能够访问该类的方式。类有如下4种访问修饰符&#xff0c;在创建类时用于类的声明&#xff1a; 1、public: 当一个类被声明为public时&#xff0c;它可以从任何其他类中被访问&#xff0c;无论这些类位于哪个包中。通常&am…
阅读更多...
一台服务器，最大支持的TCP连接数是多少？

一台服务器，最大支持的TCP连接数是多少？

一个服务端进程最大能支持多少条 TCP 连接&#xff1f; 一台服务器最大能支持多少条 TCP 连接&#xff1f; 一、原理 TCP 四元组的信息&#xff1a;源IP、源端口、目标IP、目标端口。 一个服务端进程最大能支持的 TCP 连接个数的计算公式&#xff1a;最大tcp连接数客户端的IP…
阅读更多...
最新文章

Copyright @ 2022~2023