数据结构--堆（图文）

在开始学习堆之前，我们要先简单了解二叉树

二叉树

一棵二叉树是结点的一个有限集合，该集合:

  1. 为空
  2. 由一个根结点加上两棵子树（左子树和右子树）
    在这里插入图片描述

特殊的二叉树：

  1. 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是 (2^k)-1，则它就是满二叉树。
  2. 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K
    的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。
    在这里插入图片描述

堆

堆就是上面描述的完全二叉树的一种，完全二叉树就是除了最后一层外，其他层节点数达到最大。

堆与普通的完全二叉树结构相似，但存在大小堆的性质

  • 大堆：树任何一个父节点>=子节点

  • 小堆：树任何一个父节点<=子节点
    在这里插入图片描述

堆的主要操作包括：

  1. 插入：将新元素添加到堆中，同时保持堆的性质。
  2. 删除堆顶元素：删除堆顶元素，同时保持堆的性质。
  3. 获取堆顶元素值：返回堆顶元素的值但不删除它。
  4. 调整堆（向上调整/向下调整）：将一个数组或部分数组调整成堆的形状。

堆一些应用实例：

  • 堆排序（Heap Sort）：堆排序算法利用堆数据结构对数组进行排序。它的时间复杂度为O(NlogN)，在特定情况下，它可能比快速排序还要快。
  • 优先队列（Priority Queue）：在任务调度等场景中，堆可以作为优先队列实现，确保优先级高的任务先执行。
  • 快速查找问题：例如，在大量数据中找出前K个最大或最小的元素，尤其是在内存受限的情况下，堆是一个有效的解决方案。

堆的实现

我们今天实现一个小堆，并利用这个小堆实现一个简单的堆排序。
首先创建三个文件：

Heap.h —— 用于声明函数的头文件。
Heap.c —— 堆主要函数的实现。
test.c——测试堆，并实现简单堆排序。

创建堆

堆在逻辑上是二叉树的结构，但在实际上是数组结构
在这里插入图片描述

typedef int HPDataType;//方便后需更改数据类型
typedef struct Heap
{
	HPDataType* _a;
	int _size;
	int _capacity;
}Heap;

堆的初始化

//堆的初始化
void HeapInit(Heap* hp)
{
	assert(hp);
	hp->_a = NULL;
	hp->_capacity = hp->_size = 0;
}

堆的销毁

// 堆的销毁
void HeapDestory(Heap* hp)
{
	assert(hp);
	free(hp->_a);
	hp->_a = NULL;
	hp->_capacity = hp->_size = 0;
}

调整堆

交换数据

单独封装交换函数便于使用

//交换数据
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 = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
向下调整

因为我们要建立小堆，在删除堆顶元素时，我们需要将堆顶和堆尾交换位置然后删除堆尾，为了满足小堆的性质，也就是父节点>=子节点。所以从堆顶向下只要遇到父节点<子节点的情况，我们就交换这两个节点，然后向下更新父亲和孩子的位置，继续循环查看父节点<子节点的情况，直到交换上来的这个数据到正确的地方。
在这里插入图片描述

//向下调整
void AdjustDown(HPDataType* a, int n, int parent)//n是堆元素个数
{
	int child = (parent * 2) + 1;//左孩子
	while (child < n)
	{//child+1<n防止越界访问
		if ((child + 1 < n) && (a[child] > a[child + 1]))//假设法找出较小的孩子
			child++;
		if (a[parent] > a[child])
		{
			Swap(&a[parent], &a[child]);
			parent = child;
			child = (parent * 2) + 1;
		}
		else
		{
			break;
		}
	}
}

堆的插入

没有空间开辟空间，然后将数据尾插，再向上调整让小堆恢复其性质

// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{
	assert(hp);
	if (hp->_capacity == hp->_size)
	{
		int newcapacity = hp->_capacity == 0 ? 4 : 2 * hp->_capacity;
		HPDataType* tmp = (HPDataType*)realloc(hp->_a, sizeof(HPDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc");
			exit(1);
		}
		hp->_capacity = newcapacity;
		hp->_a = tmp;
	}
	hp->_a[hp->_size] = x;
	hp->_size++;
	AdjustUp(hp->_a, hp->_size - 1);

}

堆的删除

准确来说是删除堆顶，先将堆顶和堆尾交换，删除堆尾（原堆顶），再向下调整让其恢复小堆的性质。

// 堆的删除
void HeapPop(Heap* hp)
{
	assert(hp);
	assert(hp->_size>0);
	Swap(&hp->_a[0], &hp->_a[hp->_size - 1]);
	hp->_size--;
	AdjustDown(hp->_a, hp->_size, 0);
}

取堆顶的数据

直接返回即可。

// 取堆顶的数据
HPDataType HeapTop(Heap* hp)
{
	assert(hp);
	assert(hp->_size>0);
	return hp->_a[0];
}

堆的数据个数

// 堆的数据个数
int HeapSize(Heap* hp)
{
	assert(hp);
	return hp->_size;
}

堆的判空

返回size == 0时的结果，因为此时堆为空

// 堆的判空
int HeapEmpty(Heap* hp)
{
	assert(hp);
	return hp->_size == 0;
}

堆源码以及简单堆排序

Heap.h

#include<stdbool.h>
#include<assert.h>
typedef int HPDataType;
typedef struct Heap
{
	HPDataType* _a;
	int _size;
	int _capacity;
}Heap;
//堆的初始化
void HeapInit(Heap* hp);
// 堆的销毁
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 堆的删除
void HeapPop(Heap* hp);
// 取堆顶的数据
HPDataType HeapTop(Heap* hp);
// 堆的数据个数
int HeapSize(Heap* hp);
// 堆的判空
int HeapEmpty(Heap* hp);
//向上调整
void AdjustUp(HPDataType* a, int child);
//向下调整
void AdjustDown(HPDataType* a, int n, int parent);
//交换数据
void Swap(HPDataType* p1, HPDataType* p2);

Heap.c

#include"Heap.h"

//堆的初始化
void HeapInit(Heap* hp)
{
	assert(hp);
	hp->_a = NULL;
	hp->_capacity = hp->_size = 0;
}
// 堆的销毁
void HeapDestory(Heap* hp)
{
	assert(hp);
	free(hp->_a);
	hp->_a = NULL;
	hp->_capacity = hp->_size = 0;
}
// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{
	assert(hp);
	if (hp->_capacity == hp->_size)
	{
		int newcapacity = hp->_capacity == 0 ? 4 : 2 * hp->_capacity;
		HPDataType* tmp = (HPDataType*)realloc(hp->_a, sizeof(HPDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc");
			exit(1);
		}
		hp->_capacity = newcapacity;
		hp->_a = tmp;
	}
	hp->_a[hp->_size] = x;
	hp->_size++;
	AdjustUp(hp->_a, hp->_size - 1);

}
// 堆的删除
void HeapPop(Heap* hp)
{
	assert(hp);
	assert(hp->_size>0);
	Swap(&hp->_a[0], &hp->_a[hp->_size - 1]);
	hp->_size--;
	AdjustDown(hp->_a, hp->_size, 0);
}
// 取堆顶的数据
HPDataType HeapTop(Heap* hp)
{
	assert(hp);
	assert(hp->_size>0);
	return hp->_a[0];
}
// 堆的数据个数
int HeapSize(Heap* hp)
{
	assert(hp);
	return hp->_size;
}
// 堆的判空
int HeapEmpty(Heap* hp)
{
	assert(hp);
	return hp->_size == 0;
}
//交换数据
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 = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
//向下调整
void AdjustDown(HPDataType* 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[parent] > a[child])
		{
			Swap(&a[parent], &a[child]);
			parent = child;
			child = (parent * 2) + 1;
		}
		else
		{
			break;
		}
	}
}

text.c(简单堆排序)

创建一个堆，把一个数据混乱的数组插入到小堆中，然后循环打印堆顶数据（堆顶数据最小），再将堆顶数据删除，最后销毁堆。注意：这里的排序只是打印出来了排序的结果，数组内部并没有真正排序

#include"heap.h"
void heap1()
{
	Heap hp;
	HeapInit(&hp);
	int arr[] = { 123,645,21433,45,24,7654,2,3,12,122 };
	for (int i = 0; i < (sizeof(arr) / sizeof(int)); i++)
	{
		HeapPush(&hp, arr[i]);
	}
	while (!HeapEmpty(&hp))
	{
		printf("%d ", HeapTop(&hp));
		HeapPop(&hp);
	}
	printf("\n");
	HeapDestory(&hp);

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

排序结果
在这里插入图片描述

将大堆变成小堆

只需要将向上调整和向下调整中if (a[child] < a[parent])改为if (a[child] > a[parent])即可。

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

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

相关文章

【高考】人生规划指南

【高考】人生规划指南

作为一个正处在这个选择的十字路口的高考考生&#xff0c;我认为在选择专业和学校时&#xff0c;要根据自己的具体情况和个人目标来权衡。首先&#xff0c;我认为专业是首要考虑因素。因为专业是直接决定未来职业发展方向的&#xff0c;如果不喜欢或者不适合的专业选择&#xf…
阅读更多...
1976 ssm 营地管理系统开发mysql数据库web结构java编程计算机网页源码Myeclipse项目

1976 ssm 营地管理系统开发mysql数据库web结构java编程计算机网页源码Myeclipse项目

一、源码特点 ssm 营地管理系统是一套完善的信息系统&#xff0c;结合springMVC框架完成本系统&#xff0c;对理解JSP java编程开发语言有帮助系统采用SSM框架&#xff08;MVC模式开发&#xff09;&#xff0c;系统具有完整的源代码和数据库&#xff0c;系统主要采用B/S模式开…
阅读更多...
C++【引用】

C++【引用】

P. S.&#xff1a;以下代码均在VS2019环境下测试&#xff0c;不代表所有编译器均可通过。 P. S.&#xff1a;测试代码均未展示头文件stdio.h的声明&#xff0c;使用时请自行添加。 博主主页&#xff1a;LiUEEEEE                        …
阅读更多...
2024年Stable Diffusion应用入门，AI绘画超详细兼职攻略，从零开始！

2024年Stable Diffusion应用入门，AI绘画超详细兼职攻略，从零开始！

. AI绘画&#xff1a; 利用AI工具在AI绘画上的应用非常广泛&#xff0c;涵盖了从艺术创作到工业设计等多个领域。 目前市面上有许多AI绘画软件和工具&#xff0c;适合不同需求的用户。 例如&#xff0c;Midjourney、DALL-E 2、Stable Diffusion、DreamStudio等都是较为知名的…
阅读更多...
docker配置容器——环境变量

docker配置容器——环境变量

很多时候&#xff0c;我们需要为运行在容器中的应用程序提供一些配置。配置通常用于允许同一个容器在完全不同的环境中运行&#xff0c;例如开发、测试或生产环境。在 Linux 中&#xff0c;配置值通常通过环境变量提供。我们已经了解到&#xff0c;在容器内运行的应用程序与其主…
阅读更多...
快手正式推出Vision Pro版本，引领虚拟现实社交新潮流

快手正式推出Vision Pro版本，引领虚拟现实社交新潮流

6月28日&#xff0c;快手正式推出其专为Apple Vision Pro打造的版本——快手vp版app&#xff0c;成为国内首批登陆Apple Vision Pro的短视频平台。 借助先进的虚拟现实技术&#xff0c;用户可以在快手上体验更真实生动的视频内容&#xff0c;无论是观看趣味短视频内容&#xf…
阅读更多...
Ubuntu20.04安装Prometheus监控系统

Ubuntu20.04安装Prometheus监控系统

环境准备&#xff1a; 服务器名称内网IP公网IPPrometheus服务器192.168.0.23047.119.21.167Grafana服务器192.168.0.23147.119.22.8被监控服务器192.168.0.23247.119.22.82 更改主机名方便辨认 hostnamectl set-hostname prometheus hostnamectl set-hostname grafana hostn…
阅读更多...
电脑文件夹里的表格删除了怎样恢复？别急，可这样做

电脑文件夹里的表格删除了怎样恢复？别急，可这样做

在日常工作中&#xff0c;我们经常会使用到各种电子表格来记录、整理和分析数据。然而&#xff0c;有时由于操作失误或其他原因&#xff0c;我们可能会不小心将电脑文件夹中的重要表格删除。面对这种情况&#xff0c;许多人可能会感到惊慌失措&#xff0c;担心数据丢失会给工作…
阅读更多...
【wsl2】WIN11借助wsl2挂载ext4磁盘

【wsl2】WIN11借助wsl2挂载ext4磁盘

我有一块ext4文件系统的硬盘&#xff0c;想要在win11上访问&#xff0c;我们可以通过wsl2进行挂载 wsl2的安装就跳过了&#xff0c;可以自行搜索安装。 安装完成后 >>> GET-CimInstance -query "SELECT * from Win32_DiskDrive"通过这个命令&#xff0c;可…
阅读更多...
2024下半年必追国漫片单，谁将问鼎巅峰？

2024下半年必追国漫片单，谁将问鼎巅峰？

随着2024年上半年的落幕&#xff0c;国漫市场再度迎来了百花齐放的盛况。从经典续作到全新IP&#xff0c;从玄幻到科幻&#xff0c;每一部作品都以其独特的魅力吸引着观众的目光。本期为大家盘点下半年值得一看的国漫佳作&#xff0c;大胆预测&#xff0c;谁将成为这场神仙打架…
阅读更多...
STM32开发方式的演变与未来展望

STM32开发方式的演变与未来展望

一、STM32开发方式的演变 自2007年STM32微控制器首次亮相以来&#xff0c;其开发方式经历了从寄存器到标准库&#xff0c;再到HAL&#xff08;硬件抽象层&#xff09;的演变。 1.寄存器开发&#xff08;2007年-2010年代初&#xff09; 最初&#xff0c;由于初期缺乏足够的软…
阅读更多...
基于NURBS曲线的数据拟合算法matlab仿真

基于NURBS曲线的数据拟合算法matlab仿真

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.本算法原理 4.1NURBS曲线基础 4.2 数据拟合原理 5.完整程序 1.程序功能描述 基于NURBS曲线的数据拟合算法,非均匀有理B样条&#xff08;Non-Uniform Rational B-Splines&#xff0c;简称NURBS&#xf…
阅读更多...
探究电子电路中的电压与电平转换

探究电子电路中的电压与电平转换

1. 引言 昨天跟好朋友讨论一个项目的时候,我朋友就给我画了一个简化版的电路图&#xff0c;如下图所示&#xff1a; 总觉得这个电路怪怪的&#xff0c;clk信号怎么直接接稳压电路呢。就产生了一个疑问&#xff0c;电平转换和电压转换的区别是啥&#xff1f;稳压电路还有升降压…
阅读更多...
endswith()方法——是否以指定子字符串结尾

endswith()方法——是否以指定子字符串结尾

自学python如何成为大佬(目录):https://blog.csdn.net/weixin_67859959/article/details/139049996?spm1001.2014.3001.5501 语法参考 endswith()方法用于检索字符串是否以指定子字符串结尾。如果是则返回True&#xff0c;否则返回False。endswith()方法的语法格式如下&…
阅读更多...
查看Windows启动时长

查看Windows启动时长

&#xff08;附图片&#xff09;电脑自带检测开机时长---查看方式_电脑开机时长命令-CSDN博客 eventvwr - Windows日志 - 系统 - 查找 - 6013.jpg
阅读更多...
Gradio 4.37.1官方教程二：Blocks

Gradio 4.37.1官方教程二：Blocks

文章目录 一、Blocks及事件监听器1.1 Blocks结构1.2 事件监听器的类型1.3 多数据流1.4 多输入组件1.5 多输出组件1.6 更新组件配置1.7 添加示例1.8 连续运行事件1.9 持续运行事件1.9.1 every参数1.9.2 load方法1.9.3 change方法 1.10 收集事件数据1.11 绑定多个触发器到同一函数…
阅读更多...
stthjpv：一款针对JWT Payload的安全保护工具

stthjpv：一款针对JWT Payload的安全保护工具

关于stthjpv stthjpv是一款针对JWT Payload的安全保护工具&#xff0c;这款工具集多种技术和思想于一身&#xff0c;可以通过不断改变相关参数值来防止Payload被解码&#xff0c;以帮助广大研究人员更好地保护JWT Payload的安全性。 除此之外&#xff0c;该工具还能够确保JWT …
阅读更多...
Vulnhub-DC 9

Vulnhub-DC 9

信息收集 arp-scan -l发现192.168.119.155 IP 段扫描端口 --服务22 端口 — 80 端口 这里22端口有一个&#xff08;filtered&#xff09;过滤的保护先针对80端口进行一个查看这是一个员工详细表 -----那就是说可以查看员工信息 发现一个查询框和一个登录框 1&#xff1a;查…
阅读更多...
信息系统项目管理师（项目整合管理）

信息系统项目管理师（项目整合管理）

项目的复杂性来源于组织的系统行为&#xff0c;人类行为以及组织或环境中的不确定性。在项目整合前&#xff0c;项目经理需要考虑项目面临的内外部环境因素&#xff0c;检查项目的特征或属性。作为项目的一种特征或熟悉&#xff0c;复杂性的含义&#xff1a;包含多个部分&#…
阅读更多...
武汉星起航：一站式服务，助力亚马逊卖家高效运营，实现收益飞跃

武汉星起航：一站式服务，助力亚马逊卖家高效运营，实现收益飞跃

在跨境电商的浪潮中&#xff0c;武汉星起航电子商务有限公司以其独特的一站式跨境电商服务&#xff0c;为众多亚马逊卖家提供了强有力的支持&#xff0c;助力他们在不断发展的市场中脱颖而出&#xff0c;实现收益的大幅提升。 武汉星起航的一站式跨境电商服务&#xff0c;以其…
阅读更多...
最新文章

Copyright @ 2022~2023