数据结构——堆的实现（详解）

呀哈喽，我是结衣。

堆的介绍

如果有一个关键码的集合K= {k0,k1,k2,…,kn-1},把它的所有元素按照完全二叉树的顺序储存方式储存在一个一维数组中，并满足：Ki<=K2i+1且ki<=K2i+2(Ki>=K2i+1且Ki>-K2i+2)i = 1,2,3…,则称为小堆（或大堆）。将节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫最小堆或小根堆。

性质

堆中某个节点的值总是不大于或不小于其父节点的值；
堆总是一棵完全二叉树。
在这里插入图片描述
大小堆如同所示。

堆的实现

介绍的话就到此为止，下面我们来进行堆的实现。无非就是那几样。

结构体的创建

typedef int HpDataType;
typedef struct heap
{
	HpDataType* a;
	int size;
	int capacity;
}HP;

是不是很熟悉，没错就是顺序表，但实现起来会比顺序表更难一些哦。

函数的声明

我们先把初始化，销毁，插入，删除等等要实现的函数声明一下：

void HpInit(HP* php);
void Hppush(HP* php, HpDataType x);
void Hpdestroy(HP* php);
void Hppop(HP* php);
bool Hpempty(HP* php);
HpDataType Hptop(HP* php);
int Hpsize(HP* php);

好像没多少函数？

初始化

和顺序表相同。

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

销毁

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

也是一样的说。

插入

这里开始就不一样了，我们要想怎么插才能维持小堆的结构。这里的插入是尾插，是直接插进去就不管了吗？
在这里插入图片描述
如果我们在最后插入的数据是一个大于等于56的数就没有问题，但是如果我们插入的是一个小于56的数呢？直接插入就不会满足小堆的结构了。
在这里插入图片描述
这里我们插入40，40比56小那么它应该是“父亲”，所以我们就要把他和56调换位置，但是如果我们再多想一想，我插入的是9呢，是不是就还要和10调换一下位置了？对的，这就是小堆的内涵，小的永远再上面。下面我们来写一下代码：

void Hppush(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 - 1);
}

中间有个扩容，我们讲过很多次了，就不展开讲了。
我们发现下面我有写了有个函数，向上调整的函数adjustup，没错上面我们讲的谁小于谁交换就要通过这个函数来实现。

向上调整

我们把size-1作为孩子传归来，这个还有一个重要的知识就是**父下标是子下标-1后除以2的结果。**这个用到是整形会自动忽略小数的机制。至于公式怎么来的，我把下标标出来了，你自己推推看就了解了。
在这里插入图片描述

void adjustup(HpDataType* a, int child)
{
	int parent = (child - 1) / 2;
	while (child>0)
	{
		if (a[child] < a[parent])
		{
			swap(a,child, parent);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
		
	}
}

里面还有一个swap函数，就是交换函数，它的实现在下面。回到adjustup，里面的判断大家应该是没有问题的吧，子与父交换后，我们就让child来到了parent的位置了，但是我们还要继续向上判断，所以parent改变为新child的父下标。
在这里插入图片描述

swap函数

void swap(HpDataType*a,int child, int parent)
{
	HpDataType tmp = a[child];
	a[child] = a[parent];
	a[parent] = tmp;
}

交换就是了

删除

在堆里删除也是一大难点，首先你来猜我们是头删还是尾删？
3
2
1
答案是头删加尾删，单纯尾删在这里没有意义，但这个头删也要用到尾删，你想想如果我们是把头删除了，后面的数再向前覆盖的话，那效率低且不说，而且亲子关系全部乱了。所以绝对不是单纯的头删，我们要把头数据和尾数据交换然后尾删。删除后再向下调整。

void Hppop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	//int child = php->size-1;
	//int parent = (child - 1) / 2;
	swap(php->a, php->size - 1, 0);
	php->size--;
	adjustdown(php->a,0,php->size);
}

向下调整

void adjustdown(HpDataType* a,int parent,int size)
{
	int child = parent * 2 + 1;
	if (a[child] > a[child + 1])
	{
		child++;
	}
	while (child<size)
	{
		if (a[parent] > a[child])
		{
			swap(a, child, parent);
			parent = child;
			child = parent * 2 + 1;
			if (a[child] > a[child + 1])
			{
				child++;
			}
		}
		else
		{
			break;
		}
	}
}

向下调整和向上调整也没太大的区别，都是判断后再交换，你只要清楚循环结束的条件就可以了。最重要的还是判断孩子中较小的数据，这里我们用的是假设法，我们先假设左孩子为小的数据，然后我们在判断如果不对就让孩子++，变成右孩子。

判空

bool Hpempty(HP* php)
{
	assert(php);
	return php->a == NULL;
}

返回顶部数据

HpDataType Hptop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	return php->a[0];
}

判断有效数据的个数

int Hpsize(HP* php)
{
	assert(php);
	return php->size;
}

测试

在这里插入图片描述

代码

heap.h

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
typedef int HpDataType;
typedef struct heap
{
	HpDataType* a;
	int size;
	int capacity;
}HP;
void HpInit(HP* php);
void Hppush(HP* php, HpDataType x);
void Hpdestroy(HP* php);
void Hppop(HP* php);
bool Hpempty(HP* php);
HpDataType Hptop(HP* php);
int Hpsize(HP* php);

heap.c

#include "heap.h"
void HpInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->capacity = 0;
	php->size = 0;
}
void Hpdestroy(HP* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->capacity = 0;
	php->size = 0;
}
void swap(HpDataType*a,int child, int parent)
{
	HpDataType tmp = a[child];
	a[child] = a[parent];
	a[parent] = tmp;
}

void adjustup(HpDataType* a, int child)
{
	int parent = (child - 1) / 2;
	while (child>0)
	{
		if (a[child] < a[parent])
		{
			swap(a,child, parent);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
		
	}
}
void Hppush(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 - 1);
}

void adjustdown(HpDataType* a,int parent,int size)
{
	int child = parent * 2 + 1;
	if (a[child] > a[child + 1])
	{
		child++;
	}
	while (child<size)
	{
		if (a[parent] > a[child])
		{
			swap(a, child, parent);
			parent = child;
			child = parent * 2 + 1;
			if (a[child] > a[child + 1])
			{
				child++;
			}
		}
		else
		{
			break;
		}
	}
}

void Hppop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	//int child = php->size-1;
	//int parent = (child - 1) / 2;
	swap(php->a, php->size - 1, 0);
	php->size--;
	adjustdown(php->a,0,php->size);
}
bool Hpempty(HP* php)
{
	assert(php);
	return php->a == NULL;
}

HpDataType Hptop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	return php->a[0];
}

int Hpsize(HP* php)
{
	assert(php);
	return php->size;
}

test.c

#include "heap.h"

int main()
{
	HP hp;
	HpInit(&hp);
	HpDataType* arr[] = { 21,141,41,1,1,42,9 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	for (int i = 0; i < sz; i++)
	{
		Hppush(&hp, arr[i]);
		
	}
	for (int i = 0; i < hp.size; i++)
	{
		printf("%d ", hp.a[i]);
	}
	printf("\n");
	printf("%d ", hp.a[Hptop(&hp)]);
	printf("\n");
	Hppop(&hp);
	Hppop(&hp);
	Hppop(&hp);
	Hppop(&hp);
	Hppop(&hp);
	Hppop(&hp);
	for (int i = 0; i < hp.size; i++)
	{
		printf("%d ", hp.a[i]);
	}
	return 0;
}

完
在这里插入图片描述

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

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

相关文章

软著项目推荐 深度学习中文汉字识别

软著项目推荐 深度学习中文汉字识别

文章目录 0 前言1 数据集合2 网络构建3 模型训练4 模型性能评估5 文字预测6 最后 0 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 &#x1f6a9; 深度学习中文汉字识别 该项目较为新颖&#xff0c;适合作为竞赛课题方向&#xff0c;学长非常推荐&#xf…
阅读更多...
【我的创作纪念日】

【我的创作纪念日】

机缘 大家好&#xff0c;我是圥忈ゼ&#xff0c; 2023 年 07 月 20 日&#xff0c;我撰写了第 1 篇技术博客&#xff1a;《我的编程未来规划》&#xff0c;也是由于我高考后的专业选择&#xff0c;和就业方向的选择&#xff0c;加上想立志成为一名专业 IT 作者&#xff0c;我结…
阅读更多...
第四节HarmonyOS 熟知开发工具DevEco Studio

第四节HarmonyOS 熟知开发工具DevEco Studio

一、设置主体样式 默认的代码主题样式是黑暗系的&#xff0c;如下图所示&#xff1a; 如果你不喜欢&#xff0c;可以按照一下步骤进行修改&#xff1a; 左上角点击Flie->Settings->Appearance&Behavior->Appearance&#xff0c;点击Theme&#xff0c;在弹出的下拉…
阅读更多...
区块链介绍

区块链介绍

区块链提供了比特币的公共账本&#xff0c;这是一个有序的、带有时间戳的交易记录。这个系统用于防止重复消费和修改之前的交易记录。 Introduction 比特币网络中的每个完全节点都独立存储只包含该节点验证的块的区块链。当多个节点在他们的区块链中都有相同的块时&#xff0…
阅读更多...
异步爬虫提速实践-在Scrapy中使用Aiohttp/Trio

异步爬虫提速实践-在Scrapy中使用Aiohttp/Trio

在构建爬虫系统时&#xff0c;提高爬虫速度是一个关键问题。而使用异步爬虫技术可以显著提升爬取效率。在本文中&#xff0c;我将与大家分享如何在Scrapy中利用Aiohttp或Trio库实现异步爬取&#xff0c;以加快爬虫的速度。让我们开始吧&#xff01; 1. 安装所需的库 首先&…
阅读更多...
SpringCloud-高级篇（五）

SpringCloud-高级篇（五）

一&#xff1a;分布式事务理论基础 原子性&#xff08;Atomicity&#xff09; 原子性是指事务是一个不可分割的工作单位&#xff0c;事务中的操作要么都发生&#xff0c;要么都不发生。 一致性&#xff08;Consistency&#xff09; 事务前后数据的完整性必须保持一致。 隔离性&…
阅读更多...
【电路笔记】-电阻器颜色代码与阻值计算

【电路笔记】-电阻器颜色代码与阻值计算

电阻器颜色代码与阻值计算 文章目录 电阻器颜色代码与阻值计算1、概述2、计算电阻器颜色代码值3、贴片电阻器 电阻器颜色编码使用色带轻松识别电阻器的电阻值及其百分比容差。 1、概述 由于有许多不同类型的电阻器可用&#xff0c;我们需要形成电阻器颜色代码系统以便能够识别…
阅读更多...
计算计能力挑战赛选择题真题（2020、2021、2022）

计算计能力挑战赛选择题真题（2020、2021、2022）

2020 1.关于联合体和结构体错误的是&#xff08;a) a.联合体union的存放顺序是所有成员都从高地址开始存放的(x) (ps:联合体union的存放顺序是所有成员都从低地址开始存放的) b.联合体中可以定义多个成员&#xff0c;联合体的大小由最大的成员的大小决定。 c.可以使用匿名…
阅读更多...
Spring Boot配置文件 Spring日志文件相关的知识

Spring Boot配置文件 Spring日志文件相关的知识

在上文中&#xff0c;小编带领大家创建了一个Spring Boot项目&#xff0c;并且成功的执行了第一个SPring Boot项目&#xff08;在网页上运行hello world&#xff09; 那么&#xff0c;本文的主要作用便是带领大家走进&#xff1a;Spring Boot配置文件 && Spring日志文件…
阅读更多...
C++：由哈希延伸出来的应用--位图和布隆过滤器

C++：由哈希延伸出来的应用--位图和布隆过滤器

文章目录 位图的概念位图的实现布隆过滤器布隆过滤器的查找布隆过滤器的删除布隆过滤器的优点 布隆过滤器的实现 本篇实现的是位图和应用 位图的概念 下面有这样的场景&#xff1a;给定40亿个数&#xff0c;现在要找这当中的一个数&#xff0c;如何寻找&#xff1f; 遍历&am…
阅读更多...
大数据平台/大数据技术与原理-实验报告--实战HDFS

大数据平台/大数据技术与原理-实验报告--实战HDFS

实验名称 实战HDFS 实验性质 &#xff08;必修、选修&#xff09; 必修 实验类型&#xff08;验证、设计、创新、综合&#xff09; 综合 实验课时 2 实验日期 2023.10.23-2023.10.27 实验仪器设备以及实验软硬件要求 专业实验室&#xff08;配有centos7.5系统的linu…
阅读更多...
智能优化算法应用：基于蝴蝶算法无线传感器网络(WSN)覆盖优化 - 附代码

智能优化算法应用：基于蝴蝶算法无线传感器网络(WSN)覆盖优化 - 附代码

智能优化算法应用&#xff1a;基于蝴蝶算法无线传感器网络(WSN)覆盖优化 - 附代码 文章目录 智能优化算法应用&#xff1a;基于蝴蝶算法无线传感器网络(WSN)覆盖优化 - 附代码1.无线传感网络节点模型2.覆盖数学模型及分析3.蝴蝶算法4.实验参数设定5.算法结果6.参考文献7.MATLAB…
阅读更多...
05-学成在线课程分类查询

05-学成在线课程分类查询

课程分类查询 界面原型 在新增课程基本信息界面中课程等级、课程类型、课程分类三处信息需要用户选择 当我们点击新增课程时,前端会请求内容管理服务中的content/course-category/tree-nodes接口获取课程分类表中的课程分类信息 响应数据模型 课程分类表course_category是一…
阅读更多...
顺序表总结

顺序表总结

&#x1f4d1;打牌 &#xff1a; da pai ge的个人主页 &#x1f324;️个人专栏 &#xff1a; da pai ge的博客专栏 ☁️宝剑锋从磨砺出&#xff0c;梅花香自苦寒来 目录 &#x1f324;️arraylist的简…
阅读更多...
redis优化秒杀和消息队列

redis优化秒杀和消息队列

redis优化秒杀 1. 异步秒杀思路1.1 在redis存入库存和订单信息1.2 具体流程图 2. 实现2.1 总结 3. Redis的消息队列3.1 基于list实现消息队列3.2 基于PubSub实现消息队列3.3 基于stream实现消息队列3.3.1 stream的单消费模式3.3.2 stream的消费者组模式 3.4 基于stream消息队列…
阅读更多...
WebUI自动化学习(Selenium+Python+Pytest框架)002

WebUI自动化学习(Selenium+Python+Pytest框架)002

新建项目 New Project 新建一个python代码文件 file-new-python file 会自动创建一个.py后缀的代码文件 注意:命名规则,包含字母、数字、下划线&#xff0c;不能以数字开头&#xff0c;不能跟python关键字或包名重复。 ********************华丽分割线********************…
阅读更多...
如何保护PPT文件禁止修改？

如何保护PPT文件禁止修改？

PPT文件会应用在会议、演讲、课件等工作生活中&#xff0c;当我们制作好了PPT之后&#xff0c;保护内容防止在演示时出错是很重要的&#xff0c;那么如何将PPT文件设置成禁止修改模式呢&#xff1f;今天分享几个方法给大家。 方法一 将PPT文件直接保存或者另存为一份文件&…
阅读更多...
自动化测试误区

自动化测试误区

数据驱动怎么玩? 数据驱动&#xff1a;因为数据的改变导致结果的改变。说人话就是&#xff0c;因为我在百度里搜索的是“selenium”导致结果就是包含了“seleniumhq.org”。因为我登录时候输入的是“zhangsan”导致的结果就是登录之后页面右上角显示“欢迎&#xff0c;zhangs…
阅读更多...
办公软件PDF转换工具 - pdftool

办公软件PDF转换工具 - pdftool

办公软件PDF转换工具 - pdftool&#xff0c;支持&#xff1a; 1、图片转PDF&#xff0c;支持图片自动压缩&#xff0c;可预览图片 2、合并PDF&#xff0c;支持多个PDF合并成一个PDF 3、PDF转图片&#xff0c;PDF的每页转成一张图片 4、OFD转PDF&#xff0c;OFD办公常用于国内的…
阅读更多...
商用车量产智能驾驶路径思考

商用车量产智能驾驶路径思考

1、商用车量产智能驾驶特点 2、量产自动驾驶路径 3、商用车ADAS法规件 4、高等级自动驾驶
阅读更多...
最新文章

Copyright @ 2022~2023