数据结构：堆的实现(C实现)

在这里插入图片描述

个人主页 ： 个人主页
个人专栏 ： 《数据结构》 《C语言》

文章目录

  • 一、堆
  • 二、实现思路
    • 1. 结构的定义
    • 2. 堆的构建 (HeapInit)
    • 3. 堆的销毁 (HeapDestroy)
    • 4. 堆的插入 (HeapPush)
    • 5. 堆的删除 (HeapPop)
    • 6. 取堆顶的数据 (HeapTop)
    • 7. 堆的数据个数 (HeapSize)
    • 8. 堆的判空 (HeapEmpty)
  • 三、代码实现
  • 总结

一、堆

当一颗完全二叉树用顺序表来存储时，其被称为堆。

  • 堆总是一棵完全二叉树
  • 堆的某个节点的值总是不大于(大堆)或不小于(小堆)其父节点的值

其可以被用来解决top k 问题 或 堆排序
在这里插入图片描述

下面就是要实现的堆的功能 重点在于堆的插入 和 堆的删除


//堆的构建
void HeapInit(Heap* hp);

//堆的销毁
void HeapDestroy(Heap* hp);

//堆的插入
void HeapPush(Heap* hp, HPDataType x);

//堆的删除
void HeapPop(Heap* hp);

//取堆顶的数据
HPDataType HeapTop(Heap* hp);

//堆的数据个数
int HeapSize(Heap* hp);

//堆的判空
bool HeapEmpty(Heap* hp);

二、实现思路

下部分的图，都以逻辑结构为主！！！
这里构建的是小堆。

1. 结构的定义

堆就是用顺序表来存储一颗完全二叉树，那么堆的结构就与顺序表的结构相同。
一个指向动态开辟空间的指针(data)，一个变量记录空间大小(capacity)，一个变量记录空间中有效数据(size)。

typedef int HPDataType;

typedef struct Heap
{
	HPDataType* data;
	int capacity;
	int size;
}Heap;

2. 堆的构建 (HeapInit)

malloc一块空间，用data记录其地址，capacity记录此时空间大小，size置0(此时空间内无有效数据)。

//堆的构建
#define SIZE 4

void HeapInit(Heap* hp)
{
	assert(hp);

	hp->data = (HPDataType*)malloc(sizeof(HPDataType) * SIZE);
	if (hp == NULL) 
	{
		perror("mallo: ");
		exit(-1);
	}

	hp->capacity = SIZE;
	hp->size = 0;
}

3. 堆的销毁 (HeapDestroy)

free掉动态开辟的空间，使capacity 和 size 置 0(此时空间大小为0)

//堆的销毁
void HeapDestroy(Heap* hp)
{
	assert(hp);

	free(hp->data);
	hp->data = NULL;

	hp->capacity = hp->size = 0;
}

4. 堆的插入 (HeapPush)

将数据插入到堆的尾部(最后一个子节点后)，然后与其父节点相比较，如果该节点小于其父节点(这里是小堆)，交换两个节点的值，直到该节点为堆顶或其父节点小于该节点。

  • 假设该节点下标是 i，那么其父节点的小标是 ( i - 1 ) / 2

在这里插入图片描述

//交换
void swap(HPDataType* a, HPDataType* b)
{
	HPDataType tmp = *a;
	*a = *b;
	*b = tmp;
}

//向上调整 假设该节点是 i，父节点是 (i - 1) / 2
void AdjustUp(HPDataType* data, int child)
{
	int parent = (child - 1) / 2;

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


//堆的插入
void HeapPush(Heap* hp, HPDataType x)
{
	assert(hp);

	//检查容量
	if (hp->capacity == hp->size)
	{
		HPDataType* tmp = (HPDataType*)realloc(hp->data ,sizeof(HPDataType) * (hp->capacity * 2));
		if (tmp == NULL)
		{
			perror("realloc:");
			exit(-1);
		}

		hp->data = tmp;
		hp->capacity *= 2;
	}

	hp->data[hp->size] = x;
	hp->size++;

	//向上调整   传入数组和出入数据的下标
	//此处是小堆
	AdjustUp(hp->data, hp->size - 1);
}

5. 堆的删除 (HeapPop)

堆的删除是删除堆顶数据。
堆顶数据和堆的尾部数据交换，size 减一，然后将新的堆顶数据与其左右孩子节点的最小值比较，如果新堆顶数据大于左右孩子节点的最小值，交换数据，再次与新的左右孩子节点的最小值
比较。直到该数据小于左右孩子的最小值，或该数据超出有效数据范围。

  • 假设某个节点的下标是 i，其左孩子节点的下标：i * 2 + 1，其右孩子的下标：i * 2 + 2
  • 删除堆顶数据，不能挪到数据将堆顶数据覆盖。如果挪到数据，那么兄弟节点可能会变成父子节点，而兄弟节点之间并不保证大小关系，可能会破坏堆的结构(这里是会破坏小堆结构)。

在这里插入图片描述

//交换
void swap(HPDataType* a, HPDataType* b)
{
	HPDataType tmp = *a;
	*a = *b;
	*b = tmp;
}


//向下调整，假设该节点是 i， 右孩子节点是 2 * i + 1，左孩子节点是 2 * i + 2
void AdjustDown(HPDataType* data, int parent, int size)
{
	int child = parent * 2 + 1;

	while (parent < size)
	{
		//防止越界                    找左右孩子中最小的
		if (child + 1 < size && data[child] > data[child + 1])
		{
			child++;
		}

		if (child < size && data[parent] > data[child])
		{
			swap(&data[parent], &data[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}



//堆的删除  首元素 与 尾元素交换，新的堆顶在向下调整
void HeapPop(Heap* hp)
{
	assert(hp);
	assert(!HeapEmpty(hp));
	
	hp->data[0] = hp->data[hp->size - 1];
	hp->size--;

	//向下调整
	AdjustDown(hp->data, 0, hp->size);
}

6. 取堆顶的数据 (HeapTop)

读取数组空间下标为0处即可。

//取堆顶的数据
HPDataType HeapTop(Heap* hp)
{
	assert(hp);

	return hp->data[0];
}

7. 堆的数据个数 (HeapSize)

堆的结构中size表示此时堆中有效数据的个数，访问size即可。

//堆的数据个数
int HeapSize(Heap* hp)
{
	assert(hp);

	return hp->size;
}

8. 堆的判空 (HeapEmpty)

size表示堆的有效数据个数，如果size == 0，表示堆为空。

//堆的判空
bool HeapEmpty(Heap* hp)
{
	assert(hp);

	return hp->size == 0;
}

三、代码实现

//Heap.c   文件


#include "Heap.h"


//堆的构建
void HeapInit(Heap* hp)
{
	assert(hp);

	hp->data = (HPDataType*)malloc(sizeof(HPDataType) * SIZE);
	if (hp == NULL) 
	{
		perror("mallo: ");
		exit(-1);
	}

	hp->capacity = SIZE;
	hp->size = 0;
}


//堆的销毁
void HeapDestroy(Heap* hp)
{
	assert(hp);

	free(hp->data);
	hp->data = NULL;

	hp->capacity = hp->size = 0;
}

//交换
void swap(HPDataType* a, HPDataType* b)
{
	HPDataType tmp = *a;
	*a = *b;
	*b = tmp;
}

//向上调整 假设该节点是 i，父节点是 (i - 1) / 2
void AdjustUp(HPDataType* data, int child)
{
	int parent = (child - 1) / 2;

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


//堆的插入
void HeapPush(Heap* hp, HPDataType x)
{
	assert(hp);

	//检查容量
	if (hp->capacity == hp->size)
	{
		HPDataType* tmp = (HPDataType*)realloc(hp->data ,sizeof(HPDataType) * (hp->capacity * 2));
		if (tmp == NULL)
		{
			perror("realloc:");
			exit(-1);
		}

		hp->data = tmp;
		hp->capacity *= 2;
	}

	hp->data[hp->size] = x;
	hp->size++;

	//向上调整   传入数组和出入数据的下标
	//此处是小堆
	AdjustUp(hp->data, hp->size - 1);
}



//向下调整，假设该节点是 i， 右孩子节点是 2 * i + 1，左孩子节点是 2 * i + 2
void AdjustDown(HPDataType* data, int parent, int size)
{
	int child = parent * 2 + 1;

	while (parent < size)
	{
		//防止越界                    找左右孩子中最小的
		if (child + 1 < size && data[child] > data[child + 1])
		{
			child++;
		}

		if (child < size && data[parent] > data[child])
		{
			swap(&data[parent], &data[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}



//堆的删除  首元素 与 尾元素交换，新的堆顶在向下调整
void HeapPop(Heap* hp)
{
	assert(hp);
	assert(!HeapEmpty(hp));
	
	hp->data[0] = hp->data[hp->size - 1];
	hp->size--;

	//向下调整
	AdjustDown(hp->data, 0, hp->size);
}



//取堆顶的数据
HPDataType HeapTop(Heap* hp)
{
	assert(hp);

	return hp->data[0];
}




//堆的数据个数
int HeapSize(Heap* hp)
{
	assert(hp);

	return hp->size;
}



//堆的判空
bool HeapEmpty(Heap* hp)
{
	assert(hp);

	return hp->size == 0;
}

//Heap.h  文件

#pragma once

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

#define SIZE 4

typedef int HPDataType;

typedef struct Heap
{
	HPDataType* data;
	int capacity;
	int size;
}Heap;


//堆的构建
void HeapInit(Heap* hp);

//堆的销毁
void HeapDestroy(Heap* hp);

//堆的插入
void HeapPush(Heap* hp, HPDataType x);

//堆的删除
void HeapPop(Heap* hp);

//取堆顶的数据
HPDataType HeapTop(Heap* hp);

//堆的数据个数
int HeapSize(Heap* hp);

//堆的判空
bool HeapEmpty(Heap* hp);

总结

以上就是我对于堆的实现！！！
在这里插入图片描述

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

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

相关文章

CentOS7安装Maven详细教程

CentOS7安装Maven详细教程

&#x1f60a; 作者&#xff1a; Eric &#x1f496; 主页&#xff1a; https://blog.csdn.net/weixin_47316183?typeblog &#x1f389; 主题&#xff1a;CentOS7安装Maven详细教程 ⏱️ 创作时间&#xff1a; 2023年08月06日 第一步&#xff1a;上传或下载安装包&#x…
阅读更多...
Oracle数据迁移

Oracle数据迁移

问题描述&#xff1a; oracle数据库的所有表结构、数据、索引等需要需从测试库迁移到正式库。 解决步骤&#xff1a; oracle数据库迁移&#xff0c;主要通过expdp从测试库所在的源服务器将指定的数据表或数据源导出为一个或多个数据文件&#xff08;.dmp文件&#xff09;&…
阅读更多...
信息安全：防火墙技术原理与应用.

信息安全：防火墙技术原理与应用.

信息安全&#xff1a;防火墙技术原理与应用. 防火墙是网络安全区域边界保护的重要技术。为了应对网络威胁&#xff0c;联网的机构或公司将自己的网络与公共的不可信任的网络进行隔离&#xff0c;其方法是根据网络的安全信任程度和需要保护的对象&#xff0c;人为地划分若干安全…
阅读更多...
大学生口才培训需求分析

大学生口才培训需求分析

标题&#xff1a;大学生口才培训需求分析 摘要&#xff1a; 本论文旨在分析大学生口才培训的需求&#xff0c;通过对大学生口才培训的重要性、现状和挑战进行研究&#xff0c;并结合相关理论和实践经验&#xff0c;提出相应的培训需求和解决方案。通过本论文的研究&#xff0c…
阅读更多...
森海塞尔为 CUPRA 首款纯电轿跑 SUV – CUPRA Tavascan 注入音频魅力

森海塞尔为 CUPRA 首款纯电轿跑 SUV – CUPRA Tavascan 注入音频魅力

森海塞尔为 CUPRA 首款纯电轿跑 SUV – CUPRA Tavascan 注入音频魅力 音频专家森海塞尔携手富有挑战精神的 CUPRA&#xff0c;雕琢时代新贵车型&#xff0c;打造畅快尽兴的驾驶体验 全球知名音频专家森海塞尔与以颠覆传统、充满激情、不甘现状而闻名的汽车品牌 CUPRA 展开合作…
阅读更多...
10人团队如何远程管理数千设备？向日葵赋能连锁行业IT管理

10人团队如何远程管理数千设备？向日葵赋能连锁行业IT管理

企业数字化转型对于连锁餐饮行业的赋能作用是巨大的&#xff0c;门店和企业总部的各种数字化系统以及智能设备的引入&#xff0c;可以有效的帮助企业实现降本增效。当然另一方面&#xff0c;大量数字化系统和设备的引入&#xff0c;也让连锁企业的IT运维管理工作迎来了更大的挑…
阅读更多...
VMware vCenter忘记密码操作，和Linus原理一致

VMware vCenter忘记密码操作，和Linus原理一致

mount -o remount,rw / passwd root ## 修改 root 密码要选择对应账户## 输入新密码&#xff0c;再输入一次新密码 umount / ## 卸载根文件系统 reboot -f ## 重新引导 vCenter
阅读更多...
Glide 的超时控制相关处理

Glide 的超时控制相关处理

作者&#xff1a;newki 前言 Glide 相信大家都不陌生&#xff0c;各种源码分析&#xff0c;使用介绍大家应该都是烂熟于心。但是设置 Glide 的超时问题大家遇到过没有。 我遇到了&#xff0c;并且掉坑里了&#xff0c;情况是这样的。 调用接口从网络拉取用户头像&#xff0c…
阅读更多...
SpringBoot复习：（31）Controller中返回的对象是如何转换成json字符串给调用者的？

SpringBoot复习：（31）Controller中返回的对象是如何转换成json字符串给调用者的？

首先&#xff0c;SpringBoot自动装配了HttpMessageConvertersAutoConfiguration这个自动配置类 而这个自动配置类又通过Import注解导入了JacksonHttpMessageConvertersConfiguration类&#xff0c; 在这个类中配置了一个类型为MappingJackson2HttpMessageConverter类型的bean…
阅读更多...
2023年，App运行小游戏，可以玩出什么创意？

2023年，App运行小游戏，可以玩出什么创意？

疫情过后&#xff0c;一地鸡毛。游戏行业的日子也不好过。来看看移动游戏收入&#xff1a;2022年&#xff0c;移动游戏收入达到920亿美元&#xff0c;同比下降6.4%。这告诉我们&#xff0c;2022年对移动游戏市场来说是一个小挫折。 但不管是下挫还是上升&#xff0c;移动游戏市…
阅读更多...
热成像技术创新，助力人工智能炼就黑夜中的火眼金睛

热成像技术创新，助力人工智能炼就黑夜中的火眼金睛

原创 | 文 BFT机器人 普渡大学&#xff08;Purdue University&#xff09;的研究人员利用他们正在申请专利的方法来改进传统的机器视觉和感知&#xff0c;从而推动机器人技术和自动控制领域的发展。 埃尔莫尔家族电气与计算机工程学院&#xff08;Elmore Family School of Ele…
阅读更多...
【链表OJ 5】合并两个有序链表

【链表OJ 5】合并两个有序链表

前言: &#x1f388;欢迎大家来到Dream_Chaser&#xff5e;的博客&#x1f388; 本文收录于 C--数据结构刷题的专栏中 -->http://t.csdn.cn/n6UEP 首先欢迎大家的来访&#xff0c;其次如有错误&#xff0c;非常欢迎大家的指正&#xff01;我会及时更正错误&#xff01; 目录…
阅读更多...
【已解决】Java 中使用 ES 高级客户端库 RestHighLevelClient 清理百万级规模历史数据

【已解决】Java 中使用 ES 高级客户端库 RestHighLevelClient 清理百万级规模历史数据

&#x1f389;工作中遇到这样一个需求场景&#xff1a;由于ES数据库中历史数据过多&#xff0c;占用太多的磁盘空间&#xff0c;需要定期地进行清理&#xff0c;在一定程度上可以释放磁盘空间&#xff0c;减轻磁盘空间压力。 &#x1f388;在经过调研之后发现&#xff0c;某服务…
阅读更多...
git的简单介绍和使用

git的简单介绍和使用

git学习 1. 概念git和svn的区别和优势1.1 区别1.2 git优势 2. git的三个状态和三个阶段2.1 三个状态&#xff1a;2.2 三个阶段&#xff1a; 3. 常用的git命令3.1 下面是最常用的命令3.2 git命令操作流程图如下&#xff1a; 4. 分支内容学习4.1 项目远程仓库4.2 项目本地仓库4.3…
阅读更多...
IPv4编址及子网划分

IPv4编址及子网划分

IPv4编址及子网划分 一、IPv4地址概述1.1、IPv4报文结构1.2、IPv4地址分类1.2.1、A类1.2.2、B类1.2.3、C类1.2.4、D类1.2.5、E类 1.3、私有IP地址1.4、特殊地址 二、子网划分2.1、子网掩码2.2、VLSM 可变长的子网掩码2.3、子网划分2.4、子网划分示例2.4.1、子网划分案例 —— A…
阅读更多...
【24择校指南】温州大学计算机考研考情分析

【24择校指南】温州大学计算机考研考情分析

温州大学(C) 考研难度&#xff08;☆&#xff09; 内容&#xff1a;23考情概况&#xff08;拟录取和复试分数人数统计&#xff09;、院校概况、23专业目录、23复试详情、各科目以及各专业考情分析。 正文1349字&#xff0c;预计阅读&#xff1a;3分钟。 2023考情概况 温州…
阅读更多...
IDEA新建类时自动设置类注释信息，署名和日期

IDEA新建类时自动设置类注释信息，署名和日期

IDEA设置路径 File --> Settings --> Editor --> File and Code Templates --> Include --> File Header 官方模板 这里 ${USER} 会读取计算机的用户名 ${DATE}是日期 ${TIME}是时间 /*** Author ${USER}* Date ${DATE} ${TIME}* Version 1.0*/
阅读更多...
探索自动化网页交互的魔力：学习 Selenium 之旅【超详细】

探索自动化网页交互的魔力：学习 Selenium 之旅【超详细】

"在当今数字化的世界中&#xff0c;网页自动化已经成为了不可或缺的技能。想象一下&#xff0c;您可以通过编写代码&#xff0c;让浏览器自动执行各种操作&#xff0c;从点击按钮到填写表单&#xff0c;从网页抓取数据到进行自动化测试。学习 Selenium&#xff0c;这一功能…
阅读更多...
Small Tip: 如何Debug Start Routine

Small Tip: 如何Debug Start Routine

我也不知道咋地&#xff0c;在generated ABAP里面打断点进不去。 我也不晓得怎么弄&#xff0c;今天反正是硬找着去弄。不晓得有没有其他好办法。有知道的小伙伴评论下吧。 1、 在DTP里面选Before Transformation&#xff0c;要去debug start routine选这个就够了。其他的随意…
阅读更多...
【Java可执行命令】（十七）JVM运行时信息动态维护工具 jinfo：一个维护 JVM 相关的配置参数和系统属性的工具，辅助故障排除、诊断和优化 ~

【Java可执行命令】（十七）JVM运行时信息动态维护工具 jinfo：一个维护 JVM 相关的配置参数和系统属性的工具，辅助故障排除、诊断和优化 ~

Java可执行命令之jinfo 1️⃣ 概念2️⃣ 优势和缺点3️⃣ 使用3.1 语法格式3.2 -flags&#xff1a;查看进程的启动参数3.3 -sysprops&#xff1a;查看进程的系统属性3.4 -flag < name>&#xff1a;查看特定虚拟机参数的值3.5 -flag [/-]< name>&#xff1a;启用或禁…
阅读更多...
最新文章

Copyright @ 2022~2023