【初阶数据结构】实现顺序结构二叉树->堆(附源码)

文章目录

须知

💬 欢迎讨论:如果你在学习过程中有任何问题或想法,欢迎在评论区留言,我们一起交流学习。你的支持是我继续创作的动力!

👍 点赞、收藏与分享:觉得这篇文章对你有帮助吗?别忘了点赞、收藏并分享给更多的小伙伴哦!你们的支持是我不断进步的动力!
🚀 分享给更多人:如果你觉得这篇文章对你有帮助,欢迎分享给更多对数据结构感兴趣的朋友,让我们一起进步!

⼀般堆使⽤顺序结构的数组来存储数据,堆是⼀种特殊的⼆叉树,具有⼆叉树的特性的同时,还具备其他的特性。
 1.堆的概念与结构
如果有⼀个关键码的集合 K = { k 0 , k 1 , k 2 , ... k n −1 } ,把它的所有元素按完全⼆叉树的顺序存储⽅式存储,在⼀个⼀维数组中,并满⾜: K i <= K 2∗ i +1 K i >= K 2∗ i +1 K i <= K 2∗ i +2 ),i = 0、 1 2... ,则称为⼩堆(或⼤堆)。将根结点最⼤的堆叫做最⼤堆或⼤根堆,根结点最⼩的堆
叫做最⼩堆或⼩根堆。
1.1 堆的性质
堆中某个结点的值总是不⼤于或不⼩于其⽗结点的值;
堆总是⼀棵完全⼆叉树。
1.1.1 ⼆叉树性质
对于具有 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 否则⽆右孩⼦
2 堆的模拟实现
底层:使用数组,进行了特殊的处理成为堆。

下面将以 建立小堆为示例:

heap.h头文件下的函数声明和其它头文件

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

//定义堆的结构---数组

typedef int HPDataType;

typedef struct Heap
{
	HPDataType* arr;
	int size;//有效的数据个数
	int capacity;//空间大小
}HP;

void HPInit(HP* php);
void HPDestroy(HP* php);

void HPPush(HP* php, HPDataType x);
void HPPop(HP* php);

HPDataType HPTop(HP* php);
// 判空
bool HPEmpty(HP* php);

 测试文件:

#include"Heap.h"

void test01()
{
	HP hp;
	HPInit(&hp);
	
	int arr[] = { 17,20,10,13,19,15 };
	for (int i = 0; i < 6; i++)
	{
		HPPush(&hp, arr[i]);
	}

	//HPPop(&hp);

	while (!HPEmpty(&hp))
	{
		printf("%d ", HPTop(&hp));
		HPPop(&hp);
	}


	HPDestroy(&hp);
}

int main()
{
	test01();
	return 0;
}

heap.c函数的实现方法(重点

2.1 堆的初始化和销毁
void HPInit(HP* php)//初始化
{
	assert(php);
	php->arr = NULL;
	php->size = php->capacity = 0;
}

void HPDestroy(HP* php)//销毁
{
	assert(php);
	if (php->arr)
		free(php->arr);

	php->arr = NULL;
	php->size = php->capacity = 0;
}
2.2 入堆操作
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, newCapacity * sizeof(HPDataType));
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);
		}
		php->arr = tmp;
		php->capacity = newCapacity;
	}
	php->arr[php->size] = x;
	
	AdjustUp(php->arr, php->size);

	++php->size;
}
2.2.1 向上调整算法

入堆之后,可能现在堆的数据不符合小堆或大堆的特性,需要从新调整堆的结构。

因此向上调整算法产生。

将新数据插⼊到数组的尾上,再进⾏向上调整算法,直到满⾜堆。
向上调整算法
先将元素插⼊到堆的末尾,即最后⼀个孩⼦之后
插⼊之后如果堆的性质遭到破坏,将新插⼊结点顺着其双双亲往上调整到合适位置即可

步骤(如下图)

代码如下:

void AdjustUp(HPDataType* arr,int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)//不需要等于,child只要走到根节点的位置,根节点没有父节点不需要交换
	{
		if (arr[child] < arr[parent])
		{
			Swap(&arr[parent], &arr[child]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}	
}
2.3 堆的判空
// 判空
bool HPEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}
2.4 出堆

将堆顶与最后一个数据交换,交换完成有效数据个数-1,在进行向下调整算法,因为可能删除后的数据结构不符合堆的特性。

出堆(删除数据):只能删除堆顶数据。

void HPPop(HP* php)
{
	assert(php && php->size);

	//arr[0]  arr[size-1]
	Swap(&php->arr[0], &php->arr[php->size - 1]);
	--php->size;
	AdjustDown(php->arr, 0, php->size);
}
 2.4.1 向下调整算法
void AdjustDown(HPDataType* arr, int parent, int n)
{
	int child = parent * 2 + 1;//左孩子
	//while (parent < n)
	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;
		}
	}
}

2.5 取堆顶数据

HPDataType HPTop(HP* php)
{
	assert(php && php->size);
	return php->arr[0];
}
2.6 获取堆有效数据个数
//获取堆中有效数据个数
size_t HPsize(HP* php)
{
	return php->size;
}

(附源码)

#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"

void HpInit(HP* php)
{
	assert(php);
	php->arr = NULL;
	php->capacity = php->size = 0;
}

void Hpdestroy(HP* php)
{
	assert(php);
	if (php->arr)
		free(php->arr);
		php->arr = NULL;
	php->capacity = php->size = 0;
}

void swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}

//时间复杂度logn
void AdjustUp(HpDataType* arr,int child)
{
	int parent = (child - 1) / 2;

	while (child>0)
	{
		//if (arr[child] > arr[parent])//升序
		if (arr[child] < arr[parent])//降序
		{
			swap(&arr[child], &arr[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else {
			break;
		}
	}
}

void AdjustDown(HpDataType* arr,int parent , int n)
{
	int child = 2 * parent + 1;//左孩子

	while (child < n)
	{
		//if (child + 1 < n && arr[child] > arr[child + 1])//降序
		if (child + 1 < n && arr[child] < arr[child + 1])//升序->建大堆
		{
			child++;
		}
		if (arr[child] > arr[parent])//升序
		//if (arr[child] < arr[parent])//降序
		{
			swap(&arr[parent], &arr[child]);
			parent = child;
			child = 2 * parent + 1;
		}
		else
		{
			break;
		}
	}
}

void HpPop(HP* php)//出堆:出的是堆顶的数据
{
	assert(php && php->arr);

	swap(&php->arr[0], &php->arr[php->size - 1]);
	--php->size;

	AdjustDown(php->arr, 0, php->size);
}


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

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

	return php->arr[0];
}


void HpPush(HP* php, HpDataType x)
{
	assert(php);
	//扩容
	if (php->capacity == php->size)
	{
		int newCapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
		HpDataType* tmp = (HpDataType*)realloc(php->arr, newCapacity * sizeof(HpDataType));
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);
		}
		php->arr = tmp;
		php->capacity = newCapacity;
	}
	php->arr[php->size] = x;
	//建小堆
	AdjustUp(php->arr, php->size);
	++php->size;
}

//获取堆中有效数据个数
size_t HPsize(HP* php)
{
	return php->size;
}

相信通过这篇文章你对数据结构(堆)的有了初步的了解。如果此篇文章对你学习数据结构有帮助,期待你的三连,你的支持就是我创作的动力!!!

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

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

相关文章

CSS基础学习篇——选择器

学习文档连接&#xff1a;CSS层叠样式表 1.全局选择器&#xff1a;* * {margin: 0;padding: 0;font-size: 18px; }2.类&#xff08;clss&#xff09;选择器&#xff0c;以 . 开头 .container {display: flex;justify-content: space-around;align-items: center;width: 1200…

shodan(五)连接Mongodb数据库Jenkinsorg、net、查看waf命令

声明&#xff1a;学习素材来自b站up【泷羽Sec】&#xff0c;侵删&#xff0c;若阅读过程中有相关方面的不足&#xff0c;还请指正&#xff0c;本文只做相关技术分享,切莫从事违法等相关行为&#xff0c;本人一律不承担一切后果 引言&#xff1a; 1.Shodan 是一个专门用于搜索连…

探索PickleDB:Python中的轻量级数据存储利器

文章目录 探索PickleDB&#xff1a;Python中的轻量级数据存储利器1. 背景&#xff1a;为什么选择PickleDB&#xff1f;2. PickleDB是什么&#xff1f;3. 如何安装PickleDB&#xff1f;4. 简单的库函数使用方法创建和打开数据库设置数据获取数据删除数据保存数据库 5. 应用场景与…

高效自动化测试,引领汽车座舱新纪元——实车篇

引言 作为智能网联汽车的核心组成部分&#xff0c;智能座舱不仅是驾驶者与车辆互动的桥梁&#xff0c;更是个性化、智能化体验的源泉。实车测试作为验证智能座舱功能实现、用户体验、行车安全及法规符合性的关键环节&#xff0c;能够最直接地模拟真实驾驶场景&#xff0c;确保…

光伏无人机踏勘,照亮光伏未来!

光伏电站选址地分散在各地&#xff0c;想要精准获取该地的地形特点与屋顶面积等信息&#xff0c;传统的人工踏勘耗时耗力且精度无法保证&#xff0c;难以满足现代光伏项目的规模快发发展需求。光伏无人机踏勘&#xff0c;照亮光伏未来&#xff01; 在光伏无人机智能踏勘设计系统…

uniapp数据缓存

利用uniapp做开发时&#xff0c;缓存数据是及其重要的&#xff0c;下面是同步缓存和异步缓存的使用 同步缓存 在执行同步缓存时会阻塞其他代码的执行 ① uni.setStorageSync(key, data) 设置缓存&#xff0c;如&#xff1a; uni.setStorageSync(name, 张三) ② uni.getSt…

从零开始的c++之旅——多态

1. 多态的概念 通俗来说就是多种形态。 多态分为编译时多态&#xff08;静态多态&#xff09;和运行时多态&#xff08;动态多态&#xff09;。 编译时多态主要就是我们之前提过的函数重载和函数模板&#xff0c;同名提高传不同的参数就可以调 用不同的函数&#xff0c…

nginx-proxy-manager实现反向代理+自动化证书(实战)

欢迎来到我的博客&#xff0c;代码的世界里&#xff0c;每一行都是一个故事 &#x1f38f;&#xff1a;你只管努力&#xff0c;剩下的交给时间 &#x1f3e0; &#xff1a;小破站 cnginx-proxy-manager实现反向代理自动化证书 nginx-proxy-manager是什么搭建nginx-proxy-manage…

人才画像系统:助力企业打造动态人才成长体系

在当今竞争激烈的市场环境中&#xff0c;人才已成为企业发展的核心竞争力。为了满足企业发展对人才的需求&#xff0c;人才画像系统应运而生&#xff0c;通过以岗位胜任力模型为基础定义人才标准&#xff0c;多维度采集员工信息进行人才对标和盘点&#xff0c;为企业的人才选拔…

【Hadoop和Hbase集群配置】3台虚拟机、jdk+hadoop+hbase下载和安装、环境配置和集群测试

目录 一、环境 二、虚拟机配置 三、 JDK、Hadoop、HBase的安装和配置 【安装和配置JDK】 【安装和配置Hadoop】 【安装和配置Hbase】 四、 Hadoop和HBase集群测试 【Hadoop启动测试】 【Hbase启动测试】 一、环境 OS: CentOS-7 JDK: v1.8.0_131 Hadoop: v2.7.6 Hb…

制作一个3D建模只需10秒:腾讯发布3D开源模型“混元3D”

混元 3D 模型 腾讯在科技领域投下一颗重磅炸弹&#xff0c;宣布推出混元 3D 生成大模型 “hunyuan3d - 1.0”&#xff0c;这是业界首个同时支持文字、图像生成 3D 的开源模型。它具有生成速度快、泛化能力强、可控性好等特点&#xff0c;直接引起了 AI 界众人的关注。 混元3D-1…

情怀系列国际版棋牌完整源码具备强大的多语言扩展功能,涵盖了900多款子游戏,专为全球市场的游戏开发和运营设计。

情怀棋牌源代码的服务器端使用JAVA和Node.js开发&#xff0c;采用RocketMQ作为消息队列中间件&#xff0c;有效防止服务器堵塞、消峰。数据库使用MySQL&#xff0c;媒体存储采用MongoDB&#xff0c;缓存系统使用Redis。管理后台则采用PHP语言开发。 客户端使用Cocos Creator进…

SpringBoot3集成Junit5

目录 1. 确保项目中包含相关依赖2. 配置JUnit 53. 编写测试类4、Junit5 新增特性4.1 注解4.2 断言4.3 嵌套测试4.4 总结 在Spring Boot 3中集成JUnit 5的步骤相对简单。以下是你可以按照的步骤&#xff1a; 1. 确保项目中包含相关依赖 首先&#xff0c;确保你的pom.xml文件中…

Google Guava 发布订阅模式/生产消费者模式 使用详情

目录 Guava 介绍 应用场景举例 1. 引入 Maven 依赖 2. 自定义 Event 事件类 3. 定义 EventListener 事件订阅者 4. 定义 EventBus 事件总线 5. 定义 Controller 进行测试 Guava 介绍 Guava 是一组来自 Google 的核心 Java 库&#xff0c;里面包括新的集合 类型&#xff08…

Idea如何推送项目到gitee

第一步&#xff1a;先在你的gitee创建一个仓库 第二步&#xff1a; 点击推送 点击定义远程&#xff0c;将URL换成你仓库的&#xff0c;填好你的用户名和密码 可以看到已经推送到仓库了

gdb和make工具

gdb工具&#xff1a; GDB的主要功能 断点设置&#xff1a;允许开发者在特定的代码行设置断点&#xff0c;当程序执行到该行时会自动暂停&#xff0c;方便开发者进行调试和分析。 变量查看与修改&#xff1a;在程序运行过程中&#xff0c;可以查看和修改变量的值&#xff0c;以…

一周内从0到1开发一款 AR眼镜 相机应用?

目录 1. &#x1f4c2; 前言 2. &#x1f4a0; 任务拆分 2.1 产品需求拆分 2.2 开发工作拆分 3. &#x1f531; 开发实现 3.1 代码目录截图 3.2 app 模块 3.3 middleware 模块 3.4 portal 模块 4. ⚛️ 拍照与录像 4.1 前滑后滑统一处理 4.2 初始化 View 以及 Came…

推荐一款功能强大的数据库开发管理工具:SQLite Expert Pro

SQLite Expert Professional是一个功能强大的工具&#xff0c;旨在简化SQLite3数据库的开发。 它是SQLite的一个功能丰富的管理和开发工具&#xff0c;旨在满足所有用户从编写简单SQL查询到开发复杂数据库的需求。 图形界面支持所有SQLite功能。 它包括一个可视化查询构建器&a…

C#与C++交互开发系列(十七):线程安全

前言 在跨平台开发和多线程编程中&#xff0c;线程安全是不可忽视的重要因素。C和C#中提供了各自的线程同步机制&#xff0c;但在跨语言调用中&#xff0c;如何确保数据一致性、避免数据竞争和死锁等问题&#xff0c;是开发人员必须考虑的重点。 本文将介绍在C#和C交互开发中确…