二叉树-堆实现

目录

Test.c测试代码

test1

test2

test3

🎇Test.c总代码 

Heap.h头文件&函数声明

头文件

函数声明

🎇Heap.h总代码

Heap.c函数实现 

☁HeapInit初始化

☁HeapDestroy销毁

☁HeapPush插入数据

【1】插入数据

【2】向上调整Adjustup❗

数据交换Swap

☁HeapPop删除数据

【1】交换数据

【2】删除数据

【3】向下调整Adjustdown❗

假设法找Child 

数据交换Swap

☁HeapTop堆顶元素

☁HeapSize堆元素个数

☁HeapEmpty判断为空否

🎇Heap.c总代码 

拖了很久的【堆】，本周主要学习就是【数据结构】。本章【堆】是以【小堆】为例子。

  •  堆表面是数组，内核是完全二叉树/满二叉树
  • ❗HeapPush
  • ❗HeapPop
  • 函数如果需要多次复用才会提取出来
  • free会对NULL进行检查 
  • 用循环写起来很方便的代码就不要使用递归
  • do while循环用于无论循环条件如何，循环都会执行一次
  • 步骤--注意事项--循环结束条件--时间复杂度（下篇重点讲）

Test.c测试代码

#include"Heap.h"
int main()
{
	HP php;
	//HP*ph=&php
	//test1(&php);
	test2(&php);
	test3(&php);
	return 0;
}

test1

//建堆
void test1(HP* ph)
{
	int a[] = { 4,5,3,7,8,2,1,9,10 };
	HeapInit(ph);
	int i = 0;
	for (i = 0; i < sizeof(a) / sizeof(a[0]); i++)
	{
		HeapPush(ph, a[i]);
	}
}

test2

//找出堆的前K个数字
void test2(HP* ph)
{
	int a[] = { 4,5,3,7,8,2,1,9,10 };
	HeapInit(ph);
	int i = 0;
	int k = 5;
	for (i = 0; i < sizeof(a) / sizeof(a[0]); i++)
	{
		HeapPush(ph, a[i]);
	}

	while (k--)
	{
		printf("%d ", HeapTop(ph));
		HeapPop(ph);
	}
	printf("\n");
}

 

test3

//排序--升序
void test3(HP* ph)
{
	int a[] = { 4,5,3,7,8,2,1,9,10 };
	HeapInit(ph);
	int i = 0;
	for (i = 0; i < sizeof(a) / sizeof(a[0]); i++)
	{
		HeapPush(ph, a[i]);
	}
	while (HeapEmpty(ph))//为NULLflase
	{
		printf("%d ", HeapTop(ph));
		HeapPop(ph);
	}
}

🎇Test.c总代码 

#include"Heap.h"
//建堆
void test1(HP* ph)
{
	int a[] = { 4,5,3,7,8,2,1,9,10 };
	HeapInit(ph);
	int i = 0;
	for (i = 0; i < sizeof(a) / sizeof(a[0]); i++)
	{
		HeapPush(ph, a[i]);
	}
}

//找出堆的前K个数字
void test2(HP* ph)
{
	int a[] = { 4,5,3,7,8,2,1,9,10 };
	HeapInit(ph);
	int i = 0;
	int k = 5;
	for (i = 0; i < sizeof(a) / sizeof(a[0]); i++)
	{
		HeapPush(ph, a[i]);
	}

	while (k--)
	{
		printf("%d ", HeapTop(ph));
		HeapPop(ph);
	}
	printf("\n");
}

void test3(HP* ph)
{
	int a[] = { 4,5,3,7,8,2,1,9,10 };
	HeapInit(ph);
	int i = 0;
	for (i = 0; i < sizeof(a) / sizeof(a[0]); i++)
	{
		HeapPush(ph, a[i]);
	}
	while (HeapEmpty(ph))//为NULLflase
	{
		printf("%d ", HeapTop(ph));
		HeapPop(ph);
	}
}

int main()
{
	HP php;
	//HP*ph=&php
	//test1(&php);
	test2(&php);
	test3(&php);
	return 0;
}

Heap.h头文件&函数声明

头文件

#pragma once
#include<stdio.h>
#include<string.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int HpDataType;

//定义堆结构体
typedef struct Heap
{
	HpDataType* a;
	int size;
	int capacity;
}HP;

函数声明

//常用接口
void HeapInit(HP* php);
void HeapDestroy(HP* php);
void HeapPush(HP* php,HpDataType x);
void HeapPop(HP* php);
HpDataType HeapTop(HP* php);
int HeapSize(HP* php);
bool HeapEmpty(HP* php);

🎇Heap.h总代码

#pragma once
#include<stdio.h>
#include<string.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>

typedef int HpDataType;

//定义堆结构体
typedef struct Heap
{
	HpDataType* a;
	int size;
	int capacity;
}HP;

//常用接口
void HeapInit(HP* php);
void HeapDestroy(HP* php);
void HeapPush(HP* php,HpDataType x);
void HeapPop(HP* php);
HpDataType HeapTop(HP* php);
int HeapSize(HP* php);
bool HeapEmpty(HP* php);

Heap.c函数实现 

☁HeapInit初始化

#include"Heap.h"
void HeapInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->size = 0;
	php->capacity = 0;
}

☁HeapDestroy销毁

void HeapDestroy(HP* php)
{
	assert(php);
	free(php->a);//不用担心为NULL，free会对NULL做检查
	php->size = php->capacity = 0;
}

☁HeapPush插入数据

 先插入一个10到数组的尾上，再进行向上调整算法，直到满足堆。

【1】插入数据

void HeapPush(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->a, newcapacity * sizeof(HpDataType));
		if (tmp == NULL)
		{
			printf("fail realloc");
			return;
		}
		php->capacity = newcapacity;
		php->a = tmp;
	}
	//插入数据
	php->a[php->size] = x;
	php->size++;
	//向上调整//数组，调整元素下标
	AdjustUp(php->a, php->size - 1);
}

【2】向上调整Adjustup❗

//向上调整算法
void AdjustUp(HpDataType* a, int child)
{
	int parent = (child - 1) / 2;
	while ( child > 0 )//此刻parent已经数组越界
	{
		if (a[child] < a[parent])
		{
			//交换
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (parent - 1) / 2;
		}
		else//child>=parent
		{
			break;
		}
	}
}
数据交换Swap
//交换
void Swap(HpDataType* H1, HpDataType* H2)
{
	HpDataType tmp = *H1;
	*H1 = *H2;
	*H2 = tmp;
}

☁HeapPop删除数据

删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。

//删除
void HeapPop(HP* php)
{
	assert(php);
	assert(php->size);

	//1.交换
	Swap(&php->a[0], &php->a[php->size - 1]);

	//2.删除
	php->size--;

	//3.向下调整--数组，结束条件size有关，调整的位置parent
	Adjustdown(php->a, php->size, 0);
}

【1】交换数据

	//1.交换
	Swap(&php->a[0], &php->a[php->size - 1]);

【2】删除数据

	//2.删除
	php->size--;

【3】向下调整Adjustdown❗

//3.向下调整--数组，结束条件size有关，调整的位置parent
Adjustdown(php->a, php->size, 0);
//向下调整
void Adjustdown(HpDataType* a, int size, int parent)
{
	//假设法
	int child = parent * 2 + 1;
	while (child < size )//why child < size && child+1<size
	{
		if (child + 1 < size && a[child + 1] < a[child])
		{
			child++;
		}
		//比较
		if (a[child] < a[parent])
		{
			//交换
			Swap(&a[child], &a[parent]);
			parent = child;
			child = child * 2 + 1;
		}
		else//>=
		{
			break;
		}
	}
}
假设法找Child 
	int child = parent * 2 + 1;
    if (a[child + 1] < a[child])
	{
		child++;
	}
数据交换Swap
//交换
void Swap(HpDataType* H1, HpDataType* H2)
{
	HpDataType tmp = *H1;
	*H1 = *H2;
	*H2 = tmp;
}

☁HeapTop堆顶元素

HpDataType HeapTop(HP* php)
{
	assert(php);
	assert(php->size);

	return php->a[0];
}

☁HeapSize堆元素个数

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

☁HeapEmpty判断为空否

bool HeapEmpty(HP* php)
{
	assert(php);

	return php->size != 0;//!=0是true不为NULL执行   ==0 flase 不执行
}

🎇Heap.c总代码 

#include"Heap.h"
void HeapInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->size = 0;
	php->capacity = 0;
}

void HeapDestroy(HP* php)
{
	assert(php);
	free(php->a);//不用担心为NULL，free会对NULL做检查
	php->size = php->capacity = 0;
}
//交换
void Swap(HpDataType* H1, HpDataType* H2)
{
	HpDataType tmp = *H1;
	*H1 = *H2;
	*H2 = tmp;
}

//向上调整算法
void AdjustUp(HpDataType* a, int child)
{
	int parent = (child - 1) / 2;
	while ( child > 0 )//此刻parent已经数组越界
	{
		if (a[child] < a[parent])
		{
			//交换
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (parent - 1) / 2;
		}
		else//child>=parent
		{
			break;
		}
	}
}

void HeapPush(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->a, newcapacity * sizeof(HpDataType));
		if (tmp == NULL)
		{
			printf("fail realloc");
			return;
		}
		php->capacity = newcapacity;
		php->a = tmp;
	}
	//插入数据
	php->a[php->size] = x;
	php->size++;
	//向上调整//数组，调整元素下标
	AdjustUp(php->a, php->size - 1);
}

//向下调整
void Adjustdown(HpDataType* a, int size, int parent)
{
	//假设法
	int child = parent * 2 + 1;
	while (child < size )//why child < size && child+1<size
	{
		if (child + 1 < size && a[child + 1] < a[child])
		{
			child++;
		}
		//比较
		if (a[child] < a[parent])
		{
			//交换
			Swap(&a[child], &a[parent]);
			parent = child;
			child = child * 2 + 1;
		}
		else//>=
		{
			break;
		}
	}
}
//删除
void HeapPop(HP* php)
{
	assert(php);
	assert(php->size);

	//1.交换
	Swap(&php->a[0], &php->a[php->size - 1]);

	//2.删除
	php->size--;

	//3.向下调整--数组，结束条件size有关，调整的位置parent
	Adjustdown(php->a, php->size, 0);
}

HpDataType HeapTop(HP* php)
{
	assert(php);
	assert(php->size);

	return php->a[0];
}


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

bool HeapEmpty(HP* php)
{
	assert(php);

	return php->size != 0;//!=0是true不为NULL执行   ==0 flase 不执行
}

当然，【大堆】只要改变大小符号即可，如果你不想要改变，可以使用【回调函数】！！ 

🙂感谢大家的阅读，若有错误和不足，欢迎指正！希望本周可以结束【初阶数据结构】

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

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

相关文章

nginx负载均衡案例

nginx负载均衡案例

大家好今天给大家带来nginx负载均衡实验案例,首大家先看一下我的各类版本信息。&#xff08;还有两台设备信息相同就不展示了&#xff09; 一&#xff0c;搭建nginx环境 ❶首先创建Nginx的目录并进入&#xff1a; [rootlocalhost]# mkdir /soft && mkdir /soft/nginx…
阅读更多...
java-JUC并发编程学习笔记03（尚硅谷）

java-JUC并发编程学习笔记03（尚硅谷）

线程间通信 例子&#xff1a; 对一个值1 -1交替完成&#xff0c;a的值就是1 b的值就是0 这个过程就是线程间通信 Synchronized实现&#xff1a; 虚假唤醒问题&#xff1a; 我们再添加两个线程。 我们发现我们的结果就不对了。 我们只需要使用while即可。 我们线程通信的最后一…
阅读更多...
商品主图重复如何处理？淘宝、拼多多和阿里巴巴多店铺商品上架运营技巧

商品主图重复如何处理？淘宝、拼多多和阿里巴巴多店铺商品上架运营技巧

采集铺货的时候&#xff0c;商品主图重复上架有什么影响&#xff1f; 我们在1688、阿里国际站等采集货品&#xff0c;在抖音、淘宝、京东和拼多多进行售卖的时候&#xff0c;由于货源类似&#xff0c;经常会发现商品重复&#xff0c;无法在平台获得有效流量。以企业为纬度&…
阅读更多...
【保驾护航】HarmonyOS应用开发者基础认证-题库-2024

【保驾护航】HarmonyOS应用开发者基础认证-题库-2024

通过系统化的课程学习&#xff0c;熟练掌握DevEco Studio&#xff0c;ArkTS&#xff0c;ArkUI&#xff0c;预览器&#xff0c;模拟器&#xff0c;SDK等HarmonyOS应用开发的关键概念&#xff0c;具备基础的应用开发能力。 考试说明 1、考试需实名认证&#xff0c;请在考前于个…
阅读更多...
【云原生】consul自动注册，实现负载均衡器与节点服务应用解耦，批量管理容器

【云原生】consul自动注册，实现负载均衡器与节点服务应用解耦，批量管理容器

目录 一、consul解决了什么问题&#xff1f; 二、consul的模式 三、consul的工作原理 四、实操consul连接负载均衡与容器 步骤一&#xff1a;完成consul的部署 步骤二&#xff1a;完成gliderlabs/registrator:latest镜像的拉取&#xff0c;并完成启动 步骤三&#xff1a;…
阅读更多...
二维数组的学习

二维数组的学习

前言 在前面我们学习了一维数组&#xff0c;但是有的问题需要用二位数组来解决。 二维数组常称为矩阵&#xff0c;把二维数组写成行和列的排列形式&#xff0c;可以有助于形象化的理解二维数组的逻辑结构。 一、二维数组的定义 二维数组定义的一般格式&#xff1a; 数据类型 数…
阅读更多...
最新GPT4.0使用教程，AI绘画-Midjourney绘画，GPT语音对话使用，DALL-E3文生图+思维导图一站式解决

最新GPT4.0使用教程，AI绘画-Midjourney绘画，GPT语音对话使用，DALL-E3文生图+思维导图一站式解决

一、前言 ChatGPT3.5、GPT4.0、GPT语音对话、Midjourney绘画&#xff0c;文档对话总结DALL-E3文生图&#xff0c;相信对大家应该不感到陌生吧&#xff1f;简单来说&#xff0c;GPT-4技术比之前的GPT-3.5相对来说更加智能&#xff0c;会根据用户的要求生成多种内容甚至也可以和…
阅读更多...
企业资产管理软件市场分析：预计2029年将达到91亿美元

企业资产管理软件市场分析：预计2029年将达到91亿美元

固定资产是企业资产重要的组成部分&#xff0c;是企业赖以生存的基础&#xff0c;加强固定资产管理&#xff0c;对于保障企业稳定发展有着重要意义。但是&#xff0c;不少企业因资产管理模式落后&#xff0c;以致各项资产信息无法及时传递与共享&#xff0c;资产损耗和及时维护…
阅读更多...
c语言学习笔记之字符串库函数和逗号表达式

c语言学习笔记之字符串库函数和逗号表达式

逗号表达式 #include <stdio.h>int main(){int a 10;int b 5;int c 6;int d (a 23,b a-4,c b2);printf("%d",d); }打印结果为: 逗号表达式,从左往右依次进行,将最后一个表达式的值赋值给变量. c语言字符串相关库函数 求字符串长度strlen长度不受限制的…
阅读更多...
【Linux】线程安全

【Linux】线程安全

线程安全 一、Linux线程互斥1、进程线程间的互斥相关背景概念&#xff08;1&#xff09;临界区和临界资源&#xff08;2&#xff09;互斥和原子性出现负数原因为什么--ticket不是一个原子操作&#xff1f; 2、互斥量mutex&#xff08;1&#xff09;互斥量的接口i、初始化互斥量…
阅读更多...
[嵌入式软件][入门篇][仿真平台] STM32CubeMX的搭建

[嵌入式软件][入门篇][仿真平台] STM32CubeMX的搭建

文章目录 一、简介二、STM32CubeMX的使用(1) 新建文件&#xff0c;芯片选型(2) sys设置和RCC设置(3) 配置时钟(4) 生成代码 三、仿真平台的使用 一、简介 STM32CubeMX是一种图形工具&#xff0c;通过分步过程可以非常轻松地配置STM32微控制器和微处理器&#xff0c;生成相应的初…
阅读更多...
Java项目：基于SSM框架实现的医疗企业管理系统（ssm+B/S架构+源码+数据库+毕业论文）

Java项目：基于SSM框架实现的医疗企业管理系统（ssm+B/S架构+源码+数据库+毕业论文）

一、项目简介 本项目是一套ssm815基于SSM框架实现的医疗企业管理系统&#xff0c;主要针对计算机相关专业的正在做毕设的学生与需要项目实战练习的Java学习者。 包含&#xff1a;项目源码、数据库脚本等&#xff0c;该项目附带全部源码可作为毕设使用。 项目都经过严格调试&am…
阅读更多...
【wvp】关于码率等的相关流程设计

【wvp】关于码率等的相关流程设计

目录 流程设计 前端UI大致设计 终端上的相关修改界面参考 流程设计 前端UI大致设计 终端上的相关修改界面参考
阅读更多...
Apache SeaTunnel (不含web) Window11 本机搭建（非源码）

Apache SeaTunnel (不含web) Window11 本机搭建（非源码）

启动环境 需要提前准备的(只提供作者试过且可行的方案) window11ubuntu20(wsl2) window11内置ubuntu的方式自行百度&#xff0c;此处不做陈述jdk8mysql8navicatvscode 环境准备不做过多陈述&#xff0c;以下是正式的安装启动步骤 SeaTunnel 2.3.3 资源准备 第一步: 创建文件…
阅读更多...
java8 Duration类学习

java8 Duration类学习

Duration类 官网地址 基于时间的时间量&#xff0c;例如“34.5秒”。 此类以秒和纳秒为单位对时间的量或量进行建模。它可以使用其他基于持续时间的单位访问&#xff0c;如分钟和小时。此外&#xff0c;可以使用DAYS单位&#xff0c;并将其视为完全等于24小时&#xff0c;从…
阅读更多...
5-1 A. DS串应用--KMP算法

5-1 A. DS串应用--KMP算法

题目描述 学习KMP算法&#xff0c;给出主串和模式串&#xff0c;求模式串在主串的位置 算法框架如下&#xff0c;仅供参考 输入 第一个输入t&#xff0c;表示有t个实例 第二行输入第1个实例的主串&#xff0c;第三行输入第1个实例的模式串 以此类推 输入样例&#xff1a; 3 qwe…
阅读更多...
2024-01-29 ubuntu 用脚本设置安装交叉编译工具链路径方法，设置PATH环境变量

2024-01-29 ubuntu 用脚本设置安装交叉编译工具链路径方法，设置PATH环境变量

一、设置PATH环境变量的方法,建议用~/.bash_profile的方法&#xff0c;不然在ssh登录的时候可能没有设置PATH. 二、下面的完整的脚本&#xff0c;里面的echo "export PATH$build_toolchain_path:\$PATH" >> $HOME/.bashrc 就是把交叉编译路径写写到.bashrc设置…
阅读更多...
回文子字符串的个数

回文子字符串的个数

判断一个字符串是否是一个回文除了从两端向里移动指针&#xff0c;也可以采用指针从字符串中心开始向两端延伸。即如果存在一个长度为m的回文子字符串&#xff0c;再分别向该回文两端延伸一个字符&#xff0c;并判断这两个字符是否相同&#xff0c;如果相同则找到了一个长度为m…
阅读更多...
腾讯云部署vue+node项目

腾讯云部署vue+node项目

文章目录 一、安装宝塔二、vue项目部署三、node项目部署 前言: 关于项目部署,一开始也是找了很多资料,费了点时间,所以记录一下。希望能对各位有所帮助。 一、安装宝塔 1.首先在控制台,进入云服务器的终端界面 2.输入命令和密码获取权限,并且安装宝塔界面 yum install -y w…
阅读更多...
Vue3下载WEBAPI导出的Excel文件

Vue3下载WEBAPI导出的Excel文件

webApi查询数据保存为Excel /// <summary>/// 获取LMI3D相机涂胶测量数据/// </summary>/// <returns></returns>[HttpPost(Name "GetLMI3DGlueDataToExcel")]public async Task<IActionResult> GetLMI3DGlueDataToExcel(QueryGlueM…
阅读更多...
最新文章

Copyright @ 2022~2023