【C语言】数据结构——小堆实例探究

💗个人主页💗
⭐个人专栏——数据结构学习⭐
💫点击关注🤩一起学习C语言💯💫

导读：

我们在前面学习了单链表和顺序表，以及栈和队列。
今天我们来学习小堆。
关注博主或是订阅专栏，掌握第一消息。

1. 堆的概念及结构

现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

1.1 什么是堆

堆是一种特殊的数据结构，它可以看做是一个完全二叉树（或者近似二叉树），其中每个节点的值都大于等于（或小于等于）其子节点的值。在一个最大堆中，根节点的值是最大的；在一个最小堆中，根节点的值是最小的。
在这里插入图片描述

1.2 堆的特点

堆的主要特点是：每个节点的值都大于等于（或小于等于）其子节点的值。这种特点使得堆可以快速找到最大（或最小）的元素。另外，堆还可以用于排序和优先队列等应用。
堆中兄弟节点的值之间没有关联。在堆中，节点之间的关系仅由其在树中的位置决定。

1.3 堆的结构

堆通常使用数组来实现，数组的下标代表节点在堆中的位置。根据节点在数组中的位置，可以通过简单的计算得到其父节点、左子节点和右子节点的位置。这样，在堆中插入一个新元素、删除堆顶的元素或者调整堆的结构时，只需要对数组进行简单的操作，而不需要改变整个堆的结构。

2. 堆的实现

我们需要创建两个 C文件: study.c 和 Heap.c，以及一个 头文件： Heap.h。

头文件来声明函数，一个C文件来定义函数，另外一个C文件来用于主函数main（）进行测试。

堆的常见操作包括插入元素、删除堆顶元素、堆化（调整堆的结构使其满足堆的特点）等。其中，插入元素和删除堆顶元素的时间复杂度为O(logn)，堆化的时间复杂度为O(nlogn)。

3. 代码实现

3.1 定义结构体

Heap.h：

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	int size;		//记录数组内的有效数据
	int capacity;	//记录数组空间大小
}HP;

3.2 堆的初始化

Heap.h：

//堆的初始化
void HeapInit(HP* php);

Heap.c：

//堆的初始化
void HeapInit(HP* php)
{
	//各值初始化为0
	assert(php);
	php->a = NULL;
	php->size = 0;
	php->capacity = 0;
}

3.3 堆的销毁

我们的数组空间是用malloc函数开辟的，使用完之后需要进行释放。
Heap.h：

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

Heap.c：

// 堆的销毁
void HeapDestroy(HP* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->size = 0;
	php->capacity = 0;
}

3.4 向上调整父节点与子节点

在出入数组后，我们需要对数组进行调整，以实现堆的结构特点。
在数组中，下标*2+1就是他的子节点，同样的下标-1/2就是他的父节点。
Heap.h：

//向上调整父节点与子节点
void AdjustUp(HPDataType* a, int child);

Heap.c：

//交换父节点和子节点的值
void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}
//向上调整父节点与子节点
void AdjustUp(HPDataType* a, int child)
{
	assert(a);
	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;
		}
	}
}

在这里插入图片描述

3.5 堆的插入

Heap.h：

// 堆的插入
void HeapPush(HP* php, HPDataType x);

Heap.c：

// 堆的插入
// 堆的插入
void HeapPush(HP* php, HPDataType x)
{
	assert(php);
	//首先检查数组容量是否足够
	if (php->size == php->capacity)
	{
		int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		php->a = tmp;
		php->capacity = newcapacity;
	}
	php->a[php->size] = x;
	//在插入数值后需要检查是否要进行调整
	AdjustUp(php->a, php->size);
	php->size++;
}

在这里插入图片描述
在这里插入图片描述

3.6 向下调整父节点与子节点

删除堆是删除堆顶的数据，但是我们无法直接删除第一个元素，这有极大的可能会使我们的堆崩溃，不再具有堆的特点，而在删除之后把其它数值都往前移动，再进行调整是一项很大的工作量。
所以我们可以将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。将当前的根数值调整到符合堆特点的位置去。
Heap.h：

//向下调整父节点与子节点
void AdjustDown(int* a, int size, int parent);

Heap.c：

//向下调整父节点与子节点
void AdjustDown(int* a, int size, int parent)
{
	assert(a);
	int child = parent * 2 + 1;//找到孩子节点
	while (child < size)
	{
		//找孩子中较小的一个
		if ((a[child] > a[child + 1]) && (child + 1) < size)
		{
			child += 1;
		}
		//判断两个大小进行交换
		if (a[parent] > a[child])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

3.7 堆的删除

Heap.h：

// 堆的删除
void HeapPop(HP* php);

Heap.c：

// 堆的删除
void HeapPop(HP* php)
{
	assert(php);
	//先检查数组是否有可删除的数据
	assert(php->size > 0);
	//交换首尾元素
	Swap(&php->a[php->size - 1], &php->a[0]);
	php->size--;
	//向下进行调整
	AdjustDown(php->a, php->size, 0);

}

在这里插入图片描述
在这里插入图片描述

3.8 获取堆顶元素

返回数组首元素即可
Heap.h：

// 取堆顶的数据
HPDataType HeapTop(HP* php);

Heap.c：

// 取堆顶的数据
HPDataType HeapTop(HP* php)
{
	assert(php);
	return php->a[0];
}

3.9 获取堆的个数

直接返回size的值即可
Heap.h：

// 堆的数据个数
size_t HeapSize(HP* php);

Heap.c：

// 堆的数据个数
size_t HeapSize(HP* php)
{
	assert(php);
	return php->size;
}

3.10 堆的判空

只需判断size的值是否为0，如果是，返回true，反之返回false。
Heap.h：

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

Heap.c：

// 堆的判空
bool HeapEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}

4. 代码整理

4.1 Heap.h

#define _CRT_SECURE_NO_WARNINGS 
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.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);

// 堆的数据个数
size_t HeapSize(HP* php);

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

//向上调整父节点与子节点
void AdjustUp(HPDataType* a, int child);

//向下调整父节点与子节点
void AdjustDown(int* a, int size, int parent);

//交换父节点和子节点的值
void Swap(int* child, int* parent);

4.2 Heap.c

#include "Heap.h"

//堆的初始化
void HeapInit(HP* php)
{
	//各值初始化为0
	assert(php);
	php->a = NULL;
	php->size = 0;
	php->capacity = 0;
}

// 堆的销毁
void HeapDestroy(HP* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->size = 0;
	php->capacity = 0;
}

//交换父节点和子节点的值
void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}
//向上调整父节点与子节点
void AdjustUp(HPDataType* a, int child)
{
	assert(a);
	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)
	{
		int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		php->a = tmp;
		php->capacity = newcapacity;
	}
	php->a[php->size] = x;
	//在插入数值后需要检查是否要进行调整
	AdjustUp(php->a, php->size);
	php->size++;
}


//向下调整父节点与子节点
void AdjustDown(int* a, int size, int parent)
{
	assert(a);
	int child = parent * 2 + 1;//找到孩子节点
	while (child < size)
	{
		//找孩子中较小的一个
		if ((a[child] > a[child + 1]) && (child + 1) < size)
		{
			child += 1;
		}
		//判断两个大小进行交换
		if (a[parent] > a[child])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

// 堆的删除
void HeapPop(HP* php)
{
	assert(php);
	//先检查数组是否有可删除的数据
	assert(php->size > 0);
	//交换首尾元素
	Swap(&php->a[php->size - 1], &php->a[0]);
	php->size--;
	//向下进行调整
	AdjustDown(php->a, php->size, 0);

}

// 取堆顶的数据
HPDataType HeapTop(HP* php)
{
	assert(php);
	return php->a[0];
}

// 堆的数据个数
size_t HeapSize(HP* php)
{
	assert(php);
	return php->size;
}

// 堆的判空
bool HeapEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}

4.3 study.c

void Test1()
{
	int array[] = { 27,15,19,18,28,34,65,49,25,37 };
	HP hp;
	HeapInit(&hp);
	for (int i = 0; i < sizeof(array) / sizeof(int); i++)
	{
		HeapPush(&hp, array[i]);//插入数据
	}
	int k = HeapSize(&hp);
	while (k--)
	{
		printf("%d ", HeapTop(&hp));
		HeapPop(&hp);
	}
	HeapDestroy(&hp);
}


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

在这里插入图片描述

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

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

相关文章

【初阶C++】前言

【初阶C++】前言

C前言 1. 什么是C2. C发展史3. C的重要性4. 如何学习C 1. 什么是C C语言是结构化和模块化的语言&#xff0c;适合处理较小规模的程序。对于复杂的问题&#xff0c;规模较大的程序&#xff0c;需要高度的抽象和建模时&#xff0c;C语言则不合适。为了解决软件危机&#xff0c; …
阅读更多...
“蒙企通”线上平台升级 助力内蒙古自治区民营经济发展

“蒙企通”线上平台升级 助力内蒙古自治区民营经济发展

为进一步落实《中共中央、国务院关于促进民营经济发展壮大的意见》和内蒙古自治区党委、政府《关于进一步支持民营经济高质量发展的若干措施》&#xff0c;内蒙古自治区发展改革委联合自治区工商联共同开展“自治区促进民营经济发展项目”&#xff0c;为民营经营主体拓展市场、…
阅读更多...
Python编程技巧 – 使用组合运算符

Python编程技巧 – 使用组合运算符

Python编程技巧 – 使用组合运算符 Python Programming Skills – Using Combined Operators Python通过赋值过程&#xff0c;将声明变量与赋值和而为之&#xff0c;可谓讲求效率。此外&#xff0c;在Python赋值运算符里&#xff0c;也有一个强大高效的功能&#xff0c;即复合…
阅读更多...
小傅哥星球项目拆解，如何设计复杂的抽奖流程

小傅哥星球项目拆解，如何设计复杂的抽奖流程

作者&#xff1a;小傅哥 博客&#xff1a;https://bugstack.cn 沉淀、分享、成长&#xff0c;让自己和他人都能有所收获&#xff01;&#x1f604; 大家好&#xff0c;我是技术UP主小傅哥。 我想做一个抽奖&#xff0c;但想让用户合理的别中奖。现在各个互联网产品场景中&…
阅读更多...
算法 - 二分搜索法 / 二分法（704）

算法 - 二分搜索法 / 二分法（704）

原理&#xff1a; 利用数组的有序性&#xff0c;每次取查找范围的中间点&#xff0c;缩窄一半的查找空间。比较中间值和目标值的大小&#xff0c;直到找到目标值或者查找区间为空时返回。 力扣&#xff08;LeetCode&#xff09;官网 - 全球极客挚爱的技术成长平台 题目&…
阅读更多...
图解transformer中的自注意力机制（备忘）

图解transformer中的自注意力机制（备忘）

注意力机制 在整个注意力过程中&#xff0c;模型会学习了三个权重:查询、键和值。查询、键和值的思想来源于信息检索系统。所以我们先理解数据库查询的思想。 假设有一个数据库&#xff0c;里面有所有一些作家和他们的书籍信息。现在我想读一些Rabindranath写的书&#xff1a…
阅读更多...
2. 如何通过公网IP端口映射访问到设备的vmware虚拟机的ubuntu服务器

2. 如何通过公网IP端口映射访问到设备的vmware虚拟机的ubuntu服务器

文章目录 1. 主机设备是Windows 11系统2. 安装vmware虚拟机3. 创建ubuntu虚拟机&#xff08;据说CentOS 7 明年就不维护了&#xff0c;就不用这个版本的linux了&#xff09;4. 安装nginx服务:默认端口805. 安装ssh服务:默认端口226. 设置主机 -> ubuntu的端口映射7. 设置路由…
阅读更多...
ReentrantLock详解

ReentrantLock详解

介绍 它是可重入锁的互斥锁&#xff0c;又被称为“独占锁”。它在同一时间点只能被一个线程锁持有&#xff1b;可重入表示&#xff0c;ReentrantLock锁可被同一个线程多次获取。它是通过一个FIFO的等待队列来管理获取该锁所有线程的。在“公平锁”的机制下&#xff0c;线程依次…
阅读更多...
MySQL笔记-第08章_聚合函数

MySQL笔记-第08章_聚合函数

视频链接&#xff1a;【MySQL数据库入门到大牛&#xff0c;mysql安装到优化&#xff0c;百科全书级&#xff0c;全网天花板】 文章目录 第08章_聚合函数1. 聚合函数介绍1.1 AVG和SUM函数1.2 MIN和MAX函数1.3 COUNT函数 2. GROUP BY2.1 基本使用2.2 使用多个列分组2.3 GROUP BY中…
阅读更多...
理解排序算法：冒泡排序、选择排序与归并排序

理解排序算法：冒泡排序、选择排序与归并排序

简介&#xff1a; 在计算机科学中&#xff0c;排序算法是基础且重要的概念。本文将介绍三种常见的排序方法&#xff1a;冒泡排序、选择排序和归并排序。我们将探讨它们的工作原理、特点和适用场景&#xff0c;以帮助读者更好地理解和选择合适的排序方法。 冒泡排序 冒泡排序是…
阅读更多...
cs环境部署

cs环境部署

配置搭建cs工具 两种方式 cs工具 》狐狸工具箱,微信上搜索 或者cs - OneDrive (sharepoint.com)提取密码www.ddosi.org 需要云服务器&#xff08;个人猜测如果是靶场的话&#xff0c;可以采用一台所有主机都能访问的主机作为服务端配置&#xff09; 非docker方式搭建 将c…
阅读更多...
ue5材质预览界面ue 变黑

ue5材质预览界面ue 变黑

发现在5.2和5.1上都有这个bug 原因是开了ray tracing引起的&#xff0c;这个bug真是长时间存在&#xff0c;类似的bug还包括草地上奇怪的影子和地形上的影子等等 解决方法也很简单&#xff0c;就是关闭光追&#xff08;不是…… 就是关闭预览&#xff0c;在材质界面preview sc…
阅读更多...
10基于matlab的悬臂梁四节点/八节点四边形单元有限元编程（平面单元）

10基于matlab的悬臂梁四节点/八节点四边形单元有限元编程（平面单元）

悬臂梁&#xff0c;有限元编程。基于matlab的悬臂梁四节点/八节点四边形单元有限元编程&#xff08;平面单元&#xff09;&#xff0c;程序有详细注解&#xff0c;可根据需要更改参数&#xff0c;包括长度、截面宽度和高度、密度、泊松比、均布力、集中力、单元数量等。需要就拍…
阅读更多...
【算法】递归、搜索与回溯算法

【算法】递归、搜索与回溯算法

文章目录 一. 名词解释1. 递归1.1 什么是递归&#xff1f;1.2 为什么会用到递归&#xff1f;1.3 如何理解递归&#xff1f;1.4 如何写好一个递归&#xff1f; 2. 遍历和搜索3. 回溯和剪枝 二. 递归系列专题1. 汉诺塔问题2. 合并两个有序链表3. 反转链表4. 两两交换链表中的节点…
阅读更多...
关于Anaconda的安装和环境部署（此章专为新手制定）

关于Anaconda的安装和环境部署（此章专为新手制定）

目录 Anaconda简介 一、软件下载&#xff08;地址&#x1f447;&#xff09; 2&#xff1a;点击下载 3&#xff1a;版本选择&#xff1a; 4&#xff1a;Anaconda的安装包就下载完成了 2&#xff1a;恭喜你&#xff0c;看到这里已经完成安装了 三、部署环境 1&#xff1…
阅读更多...
什么是 AWS IAM？如何使用 IAM 数据库身份验证连接到 Amazon RDS（上）

什么是 AWS IAM？如何使用 IAM 数据库身份验证连接到 Amazon RDS（上）

驾驭云服务的安全环境可能很复杂&#xff0c;但 AWS IAM 为安全访问管理提供了强大的框架。在本文中&#xff0c;我们将探讨什么是 AWS Identity and Access Management (IAM) 以及它如何增强安全性。我们还将提供有关使用 IAM 连接到 Amazon Relational Database Service (RDS…
阅读更多...
C++类模板分文件编写

C++类模板分文件编写

问题&#xff1a; 类模板中成员函数创建时机是在调用阶段&#xff0c;导致分文件编写时链接不到 解决&#xff1a; 解决方式最常用的&#xff1a;将声明和实现写到同一个文件&#xff0c;并更改后缀名为.hpp&#xff0c;hpp是约定的名称&#xff0c;并不是强制的
阅读更多...
Windows/Linux混合刻录后，Windows显示空白盘解决思路

Windows/Linux混合刻录后，Windows显示空白盘解决思路

概述 因为工作环境问题&#xff0c;需要在Windows和Linux之间来回光盘刻录&#xff0c;没有多余光盘的时候经常多次使用&#xff0c;同一光盘在Windows刻录文件到Linux&#xff0c;然后从Linux刻录文件到Windows&#xff0c;Windows用“类似U盘”格式化的光盘&#xff0c;在Wi…
阅读更多...
洛谷 P8802 [蓝桥杯 2022 国 B] 出差

洛谷 P8802 [蓝桥杯 2022 国 B] 出差

文章目录 [蓝桥杯 2022 国 B] 出差题目链接题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 提示 思路解析CODE [蓝桥杯 2022 国 B] 出差 题目链接 https://www.luogu.com.cn/problem/P8802 题目描述 A \mathrm{A} A 国有 N N N 个城市&#xff0c;编号为 1 … N …
阅读更多...
三天精通Selenium Web 自动化 - Selenium(Java)环境搭建

三天精通Selenium Web 自动化 - Selenium(Java)环境搭建

1 下载JDK JDK下载地址&#xff1a;http://www.oracle.com/technetwork/java/javase/downloads/jdk8-downloads-2133151.html 2 安装和配置JDK 安装目录尽量不要有空格 D:\Java\jdk1.8.0_91; D:\Java\jre8设置环境变量&#xff1a; “我的电脑”->右键->“属性”->…
阅读更多...
最新文章

Copyright @ 2022~2023