堆的基本操作（c语言实现）

 1.堆的基本操作

1.1定义堆

typedef int HPDataType;//堆中存储数据的类型

typedef struct Heap
{
	HPDataType* a;//用于存储数据的数组
	int size;//记录堆中已有元素个数
	int capacity;//记录堆的容量
}HP;

1.2初始化堆

然后我们需要一个初始化函数，对刚创建的堆进行初始化，注意在初始化期间要将传入数据建堆。

//初始化堆
void HeapInit(HP* php, HPDataType* a, int n)
{
	assert(php);

	HPDataType* tmp = (HPDataType*)malloc(sizeof(HPDataType)*n);//申请一个堆结构
	if (tmp == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	php->a = tmp;
	memcpy(php->a, a, sizeof(HPDataType)*n);//拷贝数据到堆中
	php->size = n;
	php->capacity = n;
	int i = 0;
	//建堆
	for (i = (php->size - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(php->a, php->size, i);
	}
}

1.3 销毁堆

 为了避免内存泄漏，使用完动态开辟的内存空间后都要及时释放该空间，所以，一个用于释放内存空间的函数是必不可少的。

//销毁堆
void HeapDestroy(HP* php)
{
	assert(php);

	free(php->a);//释放动态开辟的数组
	php->a = NULL;//及时置空
	php->size = 0;//元素个数置0
	php->capacity = 0;//容量置0
}

1.4打印堆

 打印堆中的数据，这里用的打印格式是按照堆的物理结构进行打印，即打印为一排连续的数字。

//打印堆
void HeapPrint(HP* php)
{
	assert(php);
	//按照物理结构进行打印
	int i = 0;
	for (i = 0; i < php->size; i++)
	{
		printf("%d ", php->a[i]);
	}
	printf("\n");
}

1.5堆的插入

 数据插入时是插入到数组的末尾，即树形结构的最后一层的最后一个结点，所以插入数据后我们需要运用堆的向上调整算法对堆进行调整，使其在插入数据后仍然保持堆的结构。

void HeapPush(HP* php, HPDataType x)
{
	assert(php);

	if (php->size == php->capacity)
	{
		HPDataType* tmp = (HPDataType*)realloc(php->a,
                         sizeof(HPDataType) * php->capacity*2);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		php->a = tmp;
		php->capacity *= 2;
	}

	php->a[php->size] = x;
	php->size++;

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

 这个插入的效果完全取决于AdjustUp函数是给大堆设计的还是小堆！！

1.6堆的删除

堆的删除操作通常指的是从堆中移除最大值或最小值的操作。

在最大堆中，根节点是最大的元素，而在最小堆中，根节点是最小的元素。

以下是堆的删除操作的基本思路：

  1. 首先，将堆顶元素（即根节点）与最后一个元素交换位置，即将最大值或最小值移动到数组的末尾。
  2.  然后，将堆的大小减1，即删除了原来堆顶的元素。
  3. 最后，对新的堆顶元素进行向下调整，以保持堆的性质。在最大堆中，需要将新堆顶元素与其子节点中的较大者交换，直到满足最大堆的性质；在最小堆中，需要将新堆顶元素与其子节点中的较小者交换，直到满足最小堆的性质。

通过以上步骤，可以实现堆的删除操作，并保持堆的性质不变。

//堆的删除
void HeapPop(HP* php)
{
	assert(php);
	assert(!HeapEmpty(php));

	Swap(&php->a[0], &php->a[php->size - 1]);//交换堆顶和最后一个结点的位置
	php->size--;//删除最后一个结点（也就是删除原来堆顶的元素）
	AdjustDown(php->a, php->size, 0);//向下调整
}

这段代码是堆的删除操作，基本思路如下：

1. 首先，通过断言（assert）确保传入的堆指针（php）不为空，并且堆不为空。
2. 然后，将堆顶元素（索引为0的元素）与最后一个元素进行交换，即将堆顶元素移动到数组的末尾。
3. 接着，将堆的大小减1，即删除了原来堆顶的元素。
4. 最后，调用AdjustDown函数对新的堆顶元素进行向下调整，以保持堆的性质。

1.7.获取堆的数据个数

获取堆的数据个数，即返回堆结构体中的size变量。

//获取堆中数据个数
int HeapSize(HP* php)
{
	assert(php);

	return php->size;//返回堆中数据个数
}

1.8堆的判空

堆的判空，即判断堆结构体中的size变量是否为0。

//堆的判空
bool HeapEmpty(HP* php)
{
	assert(php);

	return php->size == 0;//判断堆中数据是否为0
}

2.完整操作加测试代码

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

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;
void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType x = *p1;
	*p1 = *p2;
	*p2 = x;
}

//堆的向下调整（小堆）—— 左右子树都是小堆
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;
		}
	}
}
//初始化堆
void HeapInit(HP* php, HPDataType* a, int n)
{
	assert(php);

	HPDataType* tmp = (HPDataType*)malloc(sizeof(HPDataType) * n);//申请一个堆结构
	if (tmp == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	php->a = tmp;
	memcpy(php->a, a, sizeof(HPDataType) * n);//拷贝数据到堆中
	php->size = n;
	php->capacity = n;
	int i = 0;
	//建堆
	for (i = (php->size - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(php->a, php->size, i);
	}
}

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

	free(php->a);
	php->a = NULL;
	php->capacity = php->size = 0;
}




//堆的向上调整（小堆）
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 = (child - 1) / 2;
		}
		else//已成堆
		{
			break;
		}
	}
}


void HeapPush(HP* php, HPDataType x)
{
	assert(php);

	if (php->size == php->capacity)
	{
		HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * php->capacity * 2);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		php->a = tmp;
		php->capacity *= 2;
	}

	php->a[php->size] = x;
	php->size++;

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

//打印堆
void HeapPrint(HP* php)
{
	assert(php);
	//按照物理结构进行打印
	int i = 0;
	for (i = 0; i < php->size; i++)
	{
		printf("%d ", php->a[i]);
	}
	printf("\n");
}

void HeapPop(HP* php)
{
	assert(php);
	assert(!HeapEmpty(php));

	// 删除数据
	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;

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

HPDataType HeapTop(HP* php)
{
	assert(php);
	return php->a[0];
}



int HeapSize(HP* php)
{
	assert(php);
	return php->size;
}
int main()
{
	HP hp;
	int a[] = { 4,18,42,12,21,3,5,5,88,5,5,15,5,45,5 };
	int size = sizeof(a) / sizeof(a[0]);
	HeapInit(&hp,a,size);
	HeapPrint(&hp);

	HeapPop(&hp);
	HeapPrint(&hp);

	HeapPush(&hp, 4);
	HeapPrint(&hp);


	return 0;
}

我们可以来验证一下是不是堆

  1. 堆的向上调整和向下调整的代码一定要是匹配的，小堆的只能和小堆匹配使用，大堆的只能和大堆匹配使用，要不然就会让你十分抓马 ，我就是因为错误匹配使用就导致了痛苦了两个晚上……
  2. 还有就是大家一定要去画图去验证一下这个是不是堆，不要用眼睛看
  3. 其次就是一定要建好堆后再使用堆的向上调整和向下调整

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

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

相关文章

软件测试开发之 职业发展必备 能力模型解析

软件测试开发之 职业发展必备 能力模型解析

为什么要了解能力模型 王阳明曾在《传习录》中提到过一个思想&#xff1a;以终为始。所谓“以终为始”&#xff0c;意味着在行动的开始阶段就要考虑到最终的目标和结果&#xff0c;以此来指导自己的行动和选择。那么如果我们想在自己的行业内获取好的职业发展&#xff0c;第一…
阅读更多...
Meta更低的训练成本取得更好的性能: 多token预测(Multi-Token Prediction)

Meta更低的训练成本取得更好的性能: 多token预测(Multi-Token Prediction)

Meta提出了一种透过多token预测(Multi-token Prediction)来训练更好、更快的大型语言模型的方法。这篇论文的重点如下: 训练语言模型同时预测多个未来的token,可以提高样本效率(sample efficiency)。 在推论阶段,使用多token预测可以达到最高3倍的加速。 论文的主要贡献包括: …
阅读更多...
2024年Delphi自学培训网络资源

2024年Delphi自学培训网络资源

概述 Delphi 是一种基于 Object Pascal 的面向对象编程语言。最初&#xff0c;Delphi 是作为构建 Windows 应用程序的工具而创建的&#xff0c;并于 1995 年发布。从那时起&#xff0c;这些技术向前迈出了一大步&#xff0c;Delphi也不例外。尽管第一个用 Delphi 编写的应用程…
阅读更多...
Windows 10 中使用 Montreal-Forced-Aligner (MFA) 实现音频和文本强制对齐

Windows 10 中使用 Montreal-Forced-Aligner (MFA) 实现音频和文本强制对齐

文章目录 一、实现目标二、安装 Montreal-Forced-Aligner1、使用 Anaconda 虚拟环境2、修改默认下载路径3、安装 montreal-forced-aligner 及相关第三方包4、验证是否安装成功 三、下载声学模型和发音词典1、命令行方式下载2、手动方式下载 四、强制对齐1、准备音频及对应文本2…
阅读更多...
docker学习笔记（三）搭建NFS服务实验

docker学习笔记（三）搭建NFS服务实验

目录 什么是NFS 简单架构​编辑 一.搭建nfs服务器 二.新建共享目录和网页文件 三.设置共享目录 四&#xff1a;创建使用nfs共享目录的卷 五&#xff1a;创建容器使用nfs-web-1卷 六&#xff1a;测试访问 七&#xff1a;是否同步测试 什么是NFS NFS 服务器&#xff1a;ne…
阅读更多...
人工智能将改变科研？从胰腺癌早筛到新药研发

人工智能将改变科研？从胰腺癌早筛到新药研发

去年底英国《自然》杂志刊文预测的2024年十大科学进展中&#xff0c;人工智能的进步和ChatGPT人工智能占据前两位。那么&#xff0c;人工智能对于科学而言&#xff0c;它的哪些成果将带来有益的发展&#xff1f;今天我们请知名科普作者张田勘来聊聊这个话题。 &#xff08;1&am…
阅读更多...
万兆以太网MAC设计（13）主机与FPGA之间进行PING

万兆以太网MAC设计（13）主机与FPGA之间进行PING

文章目录 前言&#xff1a;一、ICMP校验和计算二、上板效果1、终端命令行1、wireshark捕捉 前言&#xff1a; 在上板尝试进行PING操作的时候&#xff0c;发现一直是请求超时的情况&#xff0c;结果排查发现是首部校验和没有计算的问题。在UDP层&#xff0c;我们不进行校验和是…
阅读更多...
ReentrantReadWriteLock源码分析

ReentrantReadWriteLock源码分析

ReentrantReadWriteLock是基于AQS实现的读写锁&#xff0c;读锁与读锁不互斥、读锁与写锁互斥、写锁与写锁互斥。 类的继承关系 AQS提供了共享和排它两种模式&#xff0c;acquire/release、acquireShared/releaseShared 是AQS里面的两对模板方法。写锁是排它模式基于acquire/…
阅读更多...
Yii2 自动生成php代码

Yii2 自动生成php代码

文档地址&#xff1a;入门&#xff08;Getting Started&#xff09;: 用 Gii 生成代码&#xff08;Generating Code with Gii&#xff09; - Yii 2.0 权威指南 - 文档 - Yii Framework 中文网 找到配置文件&#xff0c;以我的项目为例&#xff1a; 因为的是开启了路由美化所以访…
阅读更多...
在线扭蛋机小程序：商家稳占市场的新突破口

在线扭蛋机小程序：商家稳占市场的新突破口

近几年&#xff0c;扭蛋机进入了爆发期&#xff0c;动漫、游戏的发展更是推动了市场的发展&#xff0c;我国扭蛋机正在蓬勃发展中。 不过&#xff0c;在市场规模扩大下&#xff0c;扭蛋机行业的竞争力也在同时加大&#xff0c;企业商家需要在市场竞争中寻求发展新思路&#xf…
阅读更多...
开源推荐榜【FunClip是一款完全开源、本地部署的自动化视频剪辑工具】

开源推荐榜【FunClip是一款完全开源、本地部署的自动化视频剪辑工具】

FunClip是一款完全开源、本地部署的自动化视频剪辑工具&#xff0c;通过调用阿里巴巴通义实验室开源的FunASR Paraformer系列模型进行视频的语音识别&#xff0c;随后用户可以自由选择识别结果中的文本片段或说话人&#xff0c;点击裁剪按钮即可获取对应片段的视频&#xff08;…
阅读更多...
基于EBAZ4205矿板的图像处理：12图像二值化(阈值可调)

基于EBAZ4205矿板的图像处理：12图像二值化(阈值可调)

基于EBAZ4205矿板的图像处理&#xff1a;12图像二值化(阈值可调) 我的项目是基于EBAZ4205矿板的阈值可调的图像阈值二值化处理&#xff0c;可以通过按键调整二值化的阈值&#xff0c;key1为阈值加1&#xff0c;key4为阈值减1&#xff0c;key2为阈值加10&#xff0c;key5为阈值…
阅读更多...
【AI+音视频总结】如何在几分钟内用智能工具摘取音视频精华？揭秘下一代学习和内容创作神器！

【AI+音视频总结】如何在几分钟内用智能工具摘取音视频精华？揭秘下一代学习和内容创作神器！

今天无意发现一个网站&#xff0c;可以一步到位完成AI音视频总结。 我之前对于音视频总结的步骤还是借助 工具下载 剪映来完成的。详情可以参考之前写的一篇文章 【AI应用】模仿爆款视频二次创作短视频操作步骤 。 这里介绍的网站是 BibiGPT 。 BibiGPT AI 音视频助理 - 它是…
阅读更多...
构建第一个ArkTS应用之@AppStorage：应用全局的UI状态存储

构建第一个ArkTS应用之@AppStorage：应用全局的UI状态存储

AppStorage是应用全局的UI状态存储&#xff0c;是和应用的进程绑定的&#xff0c;由UI框架在应用程序启动时创建&#xff0c;为应用程序UI状态属性提供中央存储。 和AppStorage不同的是&#xff0c;LocalStorage是页面级的&#xff0c;通常应用于页面内的数据共享。而AppStora…
阅读更多...
VMare Workstation安装ubuntu虚拟机异常问题处理

VMare Workstation安装ubuntu虚拟机异常问题处理

安装方法 ubuntu官网下载插件 异常处理 开启时报错"unable to proceed without a log file" 遇到此问题的都有一个共同点&#xff0c;工作目录路径上都带了数字&#xff0c;比如"Ubuntu 64位 01"&#xff0c;解决方法为&#xff1a; 选中"Ubuntu 64位…
阅读更多...
可视化大屏的应用：电子政务领域的巨大应用价值

可视化大屏的应用：电子政务领域的巨大应用价值

可视化大屏在电子政务领域的应用价值主要体现在以下几个方面&#xff1a; 数据监控与分析 可视化大屏可以将政务数据以图表、地图等形式展示在大屏上&#xff0c;帮助政府部门实时监控和分析各项指标和数据变化。例如&#xff0c;可以实时显示人口统计、经济指标、环境监测等…
阅读更多...
利用“AnaTraf“网络流量分析仪轻松诊断和优化网络

利用“AnaTraf“网络流量分析仪轻松诊断和优化网络

网络性能监测和诊断(NPMD)是网络管理和优化的重要环节,准确快速地定位和排除网络故障对于保障业务正常运转至关重要。作为一款专业的网络流量分析设备,AnaTraf网络流量分析仪凭借其强大的流量分析和故障诊断功能,为网络管理者提供了一个高效的网络优化解决方案。 全面掌握网络…
阅读更多...
如何将pdf文件换成3d模型？---模大狮模型网

如何将pdf文件换成3d模型？---模大狮模型网

PDF文件是一种广泛用于文档传输和共享的格式&#xff0c;但在某些情况下&#xff0c;我们可能希望将其中的内容转换为更具交互性和视觉效果的3D模型。本文将介绍如何将PDF文件转换为3D模型&#xff0c;为您展示实现这一想象的步骤。 选择合适的PDF文件&#xff1a; 首先&#…
阅读更多...
利用AnaTraf网络流量分析仪轻松解决网络故障问题

利用AnaTraf网络流量分析仪轻松解决网络故障问题

网络故障是每个企业都必须面对的头痛问题。如何快速定位并解决网络问题,不仅能提高员工工作效率,也能减少因网络问题而带来的经济损失。 AnaTraf网络流量分析仪就是为解决这一问题而问世的一款高性能网络诊断工具。它能够对网络流量进行全面的实时监控和分析,帮助网络管理员快…
阅读更多...
软考中级之数据库系统工程师笔记总结(六)多媒体基础

软考中级之数据库系统工程师笔记总结(六)多媒体基础

作者&#xff1a;Maynor 博客之星大数据领域Top1,GitHub项目awesome-chatgpt-project作者, 大厂程序员, 全网技术矩阵粉丝7w 公众号&#xff1a;Maynor996&#x1f4e2;博客主页&#xff1a;https://manor.blog.csdn.net &#x1f4e2;欢迎点赞 &#x1f44d; 收藏 ⭐留言 &am…
阅读更多...
最新文章

Copyright @ 2022~2023