数据结构二叉树顺序存储——堆

堆

  • 1.堆的概念
  • 2.堆的实现 （建小堆为例）
    • 2.1 初始化和销毁
    • 2.2 判空
    • 2.3 获得堆顶元素和堆的大小
    • 2.4 插入
    • 2.5 删除
  • 3.堆的构建（建小堆为例）

1.堆的概念

将若干数据或元素按照完全二叉树的存储方式顺序存储到一个一维数组中，在逻辑结构中（完全二叉树）满足每个根结点的值不大于或不小于它的左右孩子结点的值。满足上述条件称为小堆或大堆。

堆的性质：堆中某节点的值不大于或不小于双亲结点的值；堆在逻辑结构上是一棵完全二叉树。

比如下图是一个小堆 （数据的增删都以这个数组为例）
在这里插入图片描述

堆只需要满足双亲结点的值不大于或不小于孩子结点的值即可，左右孩子结点的值不做要求。比如上图的13和17互换位置依然是小堆。

注意，如果元素在数组中有序，则一定可以构成堆，反之不成立。

2.堆的实现 （建小堆为例）

由于堆的物理结构使用的是数组，因此定义的结构体和顺序表类似

typedef int heapDataType;

typedef struct heapNode
{
	heapDataType* array;
	int size;
	int capacity;
}heapNode;

关于堆的接口，包括初始化和销毁，插入，删除，判空，以及获取堆顶元素和堆的大小。

2.1 初始化和销毁

和顺序表非常类似，就不赘述了，重点放在插入数据和删除数据。

//初始化堆
void heapInit(heapNode* hp)
{
	assert(hp);
	hp->array = NULL;
	hp->capacity = hp->size = 0;
}

//销毁堆
void heapDestroy(heapNode* hp)
{
	assert(hp);
	hp->array = NULL;
	hp->capacity = hp->size = 0;
}

2.2 判空

由于结构体内有成员变量size，直接返回size是否等于0即可

//判空
bool heapIsEmpty(heapNode* hp)
{
	assert(hp);
	return hp->size == 0;
}

2.3 获得堆顶元素和堆的大小

根就是堆顶，在物理结构上，堆顶就是数组的首元素。因此返回数组首元素即可。

//获得堆顶数据
heapDataType heapTop(heapNode* hp)
{
	assert(hp);
	//堆不能为空
	assert(!heapIsEmpty(hp));
	return hp->array[0];
}

//获得堆的大小
int heapSize(heapNode* hp)
{
	assert(hp);
	return hp->size;
}

2.4 插入

增加数据的时候，增加在数组的最后一个位置，增加数据前为堆，增加数据后也需要还是堆。
但数据的不同，可能影响结构。
在这里插入图片描述
在数组末尾增加一个大于或等于17的值时，堆的结构不会被破坏，如果增加的数据小于17，则需要将其调整为堆。

调整需要用到向上调整算法。指的是将符合条件的数据进行上移。
调整过程为，和该结点的双亲结点的值进行比较，如果小于双亲结点的值，那么进行交换，再作为新的孩子和新的双亲结点的值比对，直到换到根节点为止。

以插入一个7为例，调整过程如下图所示。
当调整的结点处于根节点时，则不需要进行下去了，即child下标为0
在这里插入图片描述
调整过程中可能涉及到的结点为从根节点到插入的新结点上的一条路径上的结点。
我们知道，在完全二叉树中，任一结点（设下标为k）的双亲结点的下标为（k-1）/ 2

代码实现如下

//交换
void swap(heapDataType* x1, heapDataType* x2)
{
	heapDataType tmp = *x1;
	*x1 = *x2;
	*x2 = tmp;
}

//向上调整算法
void AdJustUp(heapDataType* array,int child)
{
    //双亲节点的下标
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (array[child] < array[parent])
		{
			//交换数据
			swap(&array[child], &array[parent]);
			//更新下标
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

//插入
void heapPush(heapNode* hp, heapDataType x)
{
	assert(hp);
	//容量不够,扩容
	if (hp->size == hp->capacity)
	{
		int newCapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
		//空间可能开辟失败，为保留原数据，创建新的指针变量
		heapDataType* tmp = realloc(hp->array, sizeof(heapNode) * newCapacity);
		if (tmp == NULL)
		{
			return;
		}
		//开辟成功
		hp->capacity = newCapacity;
		hp->array = tmp;
	}
	//插入数据
	hp->array[hp->size++] = x;
	//向上调整重新建堆
	AdJustUp(hp->array,hp->size-1);
}

插入数据和顺序表中完全一样，只是多了一步向上调整。

2.5 删除

堆的删除指的是删除堆顶的数据。对于数组，我们比较容易想到的是数据的挪动覆盖，但是这样会导致一个问题，就是删除数据后，堆结构被破坏的很严重。使得难以将其恢复成堆。因此这种做法不合适。

这里的做法是，将堆顶数据和最后一个数据进行交换，然后在删除。这样做虽然也会破坏堆的结构，但是破坏的程度没有那么大，可以通过算法（向下调整算法）将其恢复成堆。

刚刚我们插入了一个7，现在我们在删除一次堆顶的数据。

首先，交换首尾数据并删除，从根节点开始向下调整，找到左右孩子结点中值小的那个进行交换，在作为新的双亲结点，找新的值较小的孩子结点进行交换，直到换到叶子结点。

举例删除7，删除过程如图所示。
在这里插入图片描述
如果25处数据是15，则在进行一次交换即可。
有几个小问题需要处理，1.怎么找到较小的孩子结点。2.调整的结束条件。

对于问题1：可以使用假设法，假设左孩子值较小，在和右孩子的值进行比较，如果存在右孩子且右孩子值小，则下标加一
对于问题2：在数组中，孩子结点的下标不会超过数组大小。如果孩子结点的下标已经超过数组，说明调整的结点已经是叶子结点，则不要在进行调整了。

代码如下

//向下调整
void AdJustDown(heapDataType* array, int num_array, int parent)
{
	//孩子下标
	int child = parent * 2 + 1;
	
	while (child < num_array)
	{
	    //找到值小的孩子，if条件1指存在右孩子，条件2指右孩子值小
		if (child + 1 < num_array && array[child + 1] < array[child])
		{
			++child;
		}
		if (array[child] < array[parent])
		{
			//交换数据
			swap(&array[child], &array[parent]);
			//更新下标
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

//删除
void heapPop(heapNode* hp)
{
	assert(hp);
	//堆不能为空
	assert(!heapIsEmpty(hp));

	//交换堆的首尾数据
	swap(&hp->array[0], &hp->array[hp->size - 1]);
	hp->size--;
	//向下调整重新建堆
	AdJustDown(hp->array, hp->size, 0);
}

3.堆的构建（建小堆为例）

随机给一个数组，将这个数组构建成为堆。
这里有两种方法，第一种是依次插入数据，向上调整建堆。一个数据可以看作堆，依次插入数据后，堆结构被破坏，进行向上调整，数组遍历完全后，就构建成了堆。

int main()
{
	srand(time(NULL));
	heapNode hp;
	heapInit(&hp);

	//生成十个随机数，插入堆
	for (int i = 0; i < 10; i++)
	{
		int j = rand() % 100;
		heapPush(&hp, j);
	}

	//打印，数据符合小堆
	for (int i = 0; i < 10; i++)
	{
		printf("%d ", hp.array[i]);
	}
	printf("\n\n");
	//该操作为获取堆顶数据，打印后，在删除，最终结果为升序
	while (!heapIsEmpty(&hp))
	{
        printf("%d ", heapTop(&hp));
		heapPop(&hp);
	}
	heapDestroy(&hp);
	return 0;
}

打印结果如图
在这里插入图片描述

第二种方法为向下调整建堆。
向下调整算法有一个前提，指的是调整的结点的左右子树需要是堆。因此从根节点开始调整的方法不适用了，一个值可以看成是堆，因此从倒数的第一个非叶子结点开始向下调整。
在这里插入图片描述
将该数组打乱成25，36，10，13，17，42

向下调整建堆的过程如下图所示
在这里插入图片描述

那么第一个非叶子结点下标是多少呢？
首先，最后一个非叶子结点是最后一个结点的双亲结点，下标需要结合数组和完全二叉树的性质来计算。假设数组中元素个数为n，则最后一个元素下标为n-1，完全二叉树中，下标为n-1的双亲结点的下标为[ ( n - 1 ) -1 ] / 2 即 ( n - 2）/ 2；

调整后数组就符合堆结构了。

int main()
{
	int arr[10] = { 0 };
	//随机生成二十个树
	for (int i = 0; i < 10; i++)
	{
		arr[i] = rand() % 100 + 10;
	}
	
	//打印随机数
	for (int i = 0; i < 10; i++)
	{
		printf("%d ", arr[i]);
	}
	//向下调整建堆
	for (int j = (10 - 2) / 2; j >= 0; --j)
	{
		AdJustDown(arr, 10, j);
	}
	printf("\n\n");

	//打印调整后的数组
	for (int i = 0; i < 10; i++)
	{
		printf("%d ", arr[i]);
	}
}

打印结果如图
在这里插入图片描述

堆的介绍就先到这里了。
本篇主要介绍二叉树的顺序存储，也就是堆了，关于堆的应用（堆排序，topk问题）就留到下次在介绍吧。

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

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

相关文章

LiDAR和Camera融合的BEV感知算法-BEVFusion

LiDAR和Camera融合的BEV感知算法-BEVFusion

0. 简述 本次给大家讲解一篇非常经典的融合工作叫 BEVFusion&#xff0c;我们依旧从算法动机&开创性思路、主体结构、损失函数以及性能对比四个方面展开 BEVFusion 有两篇文章&#xff0c;本次主要讲解的是阿里和北大的&#xff1a;BEVFusion: A Simple and Robust LiDAR-…
阅读更多...
Node | Node.js 版本升级

Node | Node.js 版本升级

目录 Step1&#xff1a;下载 Step2&#xff1a;安装 Step3&#xff1a;换源 发现其他博客说的 n 模块不太行&#xff0c;所以老老实实地手动安装 Step1&#xff1a;下载 Node 中文官网&#xff1a;https://nodejs.cn/download 点击后&#xff0c;将会下载得到一个 .msi 文件…
阅读更多...
打断点调试代码的思路（找bug的思路）二分法

打断点调试代码的思路（找bug的思路）二分法

现象&#xff1a; 当断点运行到此处&#xff0c;卡死 二分法&#xff1a; 用断点把程序切段&#xff0c;前一段&#xff0c;后一段 **前一段&#xff1a;检查变量值&#xff0c;如无问题&#xff0c;则说明没有任何问题 问题必然出在后一段 后一段&#xff1a;人为检查&…
阅读更多...
了解游戏相关知识

了解游戏相关知识

个人笔记&#xff08;整理不易&#xff0c;有帮助点个赞&#xff09; 笔记目录&#xff1a;学习笔记目录_pytest和unittest、airtest_weixin_42717928的博客-CSDN博客 个人随笔&#xff1a;工作总结随笔_8、以前工作中都接触过哪些类型的测试文档-CSDN博客 目录 一&#xff1a…
阅读更多...
鸿蒙TypeScript学习第7天：【TypeScript 循环】

鸿蒙TypeScript学习第7天：【TypeScript 循环】

1、TypeScript 循环 有的时候&#xff0c;我们可能需要多次执行同一块代码。一般情况下&#xff0c;语句是按顺序执行的&#xff1a;函数中的第一个语句先执行&#xff0c;接着是第二个语句&#xff0c;依此类推。 编程语言提供了更为复杂执行路径的多种控制结构。 循环语句…
阅读更多...
Polardb代理介绍

Polardb代理介绍

代理位于数据库和应用程序之间的网络代理服务&#xff0c;转发客户端的请求到DB&#xff0c;收到DB回包在转发到客户端&#xff0c;提供多种能力&#xff0c;支持&#xff1a;读写分离、负载均衡、一致性级别、连接池、过载保护功能。对外提供地址&#xff1a;主地址和集群地址…
阅读更多...
Halcon3D倾斜平面矫正至水平面

Halcon3D倾斜平面矫正至水平面

前言 在相当多的3d检测中&#xff0c;由于各种因素的干扰&#xff0c;我们所检测的平面通常并不是一个水平面&#xff0c;或者被检测的面不是水平面的情况。尤其是在倾斜面的缺陷检测和平面度检测中&#xff0c;使用被测面与拟合基准面进行计算很难做到准确的定位到缺陷的情况…
阅读更多...
全数字化病理，“根深”才能“叶茂”

全数字化病理，“根深”才能“叶茂”

现代医学之父William Osler曾言&#xff1a;病理学乃医学之本。 作为研究人体疾病发生的原因、发病机制、病理变化以及疾病过程中机体的形态结构、功能代谢变化和病变转归的一门基础医学科学&#xff0c;病理学一直被视为基础医学与临床医学之间的“桥梁学科”&#xff0c;在医…
阅读更多...
分类预测 | Matlab实现TCN-BiGRU-Mutilhead-Attention时间卷积双向门控循环单元多头注意力机制多特征分类预测/故障识别

分类预测 | Matlab实现TCN-BiGRU-Mutilhead-Attention时间卷积双向门控循环单元多头注意力机制多特征分类预测/故障识别

分类预测 | Matlab实现TCN-BiGRU-Mutilhead-Attention时间卷积双向门控循环单元多头注意力机制多特征分类预测/故障识别 目录 分类预测 | Matlab实现TCN-BiGRU-Mutilhead-Attention时间卷积双向门控循环单元多头注意力机制多特征分类预测/故障识别分类效果基本介绍模型描述程序…
阅读更多...
Linux文件与进程交互的窥探者lsof

Linux文件与进程交互的窥探者lsof

lsof 是一个 Linux 和 UNIX 系统中的实用工具&#xff0c;用于列出系统中打开文件的所有信息。这个名字代表 “List Open Files”&#xff0c;但它也可以显示进程相关的其他信息&#xff0c;如&#xff1a; 打开的文件描述符列表 打开网络连接的列表 被进程使用的信号和内核对…
阅读更多...
HarmonyOS实战开发-为应用添加运行时权限

HarmonyOS实战开发-为应用添加运行时权限

介绍 通过AbilityAccessCtrl动态向用户申请“允许不同设备间的数据交换”的权限&#xff0c;使用设备管理实例获取周边不可信设备列表。 说明&#xff1a; 查询周边不可信设备之前&#xff0c;请确保本设备与周边设备未进行配对。如果已配对&#xff0c;则恢复出厂设置之后重新…
阅读更多...
Python中的全栈开发前端与后端的完美融合【第160篇—全栈开发】

Python中的全栈开发前端与后端的完美融合【第160篇—全栈开发】

&#x1f47d;发现宝藏 前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家。【点击进入巨牛的人工智能学习网站】。 Python中的全栈开发&#xff1a;前端与后端的完美融合 全栈开发已成为当今软件开发领域中的…
阅读更多...
Linux权限提升总结

Linux权限提升总结

几个信息收集的项目推荐 运行这几个项目就会在目标主机上收集一些敏感信息供我们参考和使用 一个综合探针&#xff1a;traitor 一个自动化提权&#xff1a;BeRoot(gtfo3bins&lolbas) 使用python2运行beroot.py就可以运行程序&#xff0c;然后就可以收集到系统中的大量信…
阅读更多...
景顺长城：《重塑与创造——2024 ai+洞察报告》

景顺长城：《重塑与创造——2024 ai+洞察报告》

近期&#xff0c;景顺长城发布了《重塑与创造——2024 ai洞察报告》,报告深入探讨了人工智能&#xff08;AI&#xff09;产业的发展现状、未来趋势以及对各行业的潜在影响。报告认为&#xff0c;AI产业发展是多层次、多浪潮的&#xff0c;目前我们处于第二阶段但未来将持续伴随…
阅读更多...
企业案例：金蝶云星空集成钉钉，帆软BI

企业案例：金蝶云星空集成钉钉，帆软BI

正文&#xff1a;在数字化转型的大潮中&#xff0c;众多企业开始探索并实践高效的数据流转与集成&#xff0c;以提升内部管理效率和决策质量。本文将以某企业为例&#xff0c;详细介绍如何通过将钉钉审批流程的数据实时同步至金蝶云星空&#xff0c;并进一步在帆软报表平台上实…
阅读更多...
缺省参数

缺省参数

缺省参数 缺省参数概念 缺省参数是声明或定义函数时为函数的参数指定一个缺省值。在调用该函数时&#xff0c;如果没有指定实 参则采用该形参的缺省值&#xff0c;否则使用指定的实参。 void Func(int a 0) {cout<<a<<endl; } int main() {Func(); // 没有传…
阅读更多...
力扣刷题Days31-2.两数相关(js)

力扣刷题Days31-2.两数相关(js)

1&#xff0c;题目 给你两个 非空 的链表&#xff0c;表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的&#xff0c;并且每个节点只能存储 一位 数字。 请你将两个数相加&#xff0c;并以相同形式返回一个表示和的链表。 你可以假设除了数字 0 之外&#xff0c;…
阅读更多...
基于ssm的企业销售人员培训系统（java项目+文档+源码）

基于ssm的企业销售人员培训系统（java项目+文档+源码）

风定落花生&#xff0c;歌声逐流水&#xff0c;大家好我是风歌&#xff0c;混迹在java圈的辛苦码农。今天要和大家聊的是一款基于ssm的企业销售人员培训系统。项目源码以及部署相关请联系风歌&#xff0c;文末附上联系信息 。 项目简介&#xff1a; 企业销售人员培训系统主要…
阅读更多...
ios应用内支付

ios应用内支付

用uniapp开发iOS应用内支付 准备前端代码服务器端处理如果iOS支付遇到问题实在解决不了&#xff0c;可以联系我帮忙解决&#xff0c;前端后端都可以解决&#xff08;添加的时候一定要备注咨询iOS支付问题&#xff09; 准备前端代码 获取支付通道 (uni.getProvider) uni.getPr…
阅读更多...
idea端口占用

idea端口占用

报错&#xff1a;Verify the connector‘s configuration, identify and stop any process that‘s listening on port XXXX 翻译&#xff1a; 原因&#xff1a; 解决&#xff1a; 一、重启大法 二、手动关闭 启动spring项目是控制台报错&#xff0c;详细信息如下&#xff…
阅读更多...
最新文章

Copyright @ 2022~2023