【算法与数据结构】深入解析二叉树（二）之堆结构实现

请添加图片描述

文章目录

  • 📝二叉树的顺序结构及实现
    • 🌠 二叉树的顺序结构
    • 🌠 堆的实现
    • 🌠 堆的实现
      • 🌉堆向下调整算法
      • 🌉堆的创建
      • 🌉建堆时间复杂度
      • 🌉堆的插入
      • 🌉堆的删除
    • 🌠堆向上调整算法
      • 🌉堆的接口
    • 🌠堆的实现
    • 🌠堆的实现代码测试
  • 🚩总结

📝二叉树的顺序结构及实现

🌠 二叉树的顺序结构

普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。
在这里插入图片描述

🌠 堆的实现

堆（heap）是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：
堆的物理结构本质上是顺序存储的，是线性的。但在逻辑上不是线性的，是完全二叉树的这种逻辑储存结构。 堆的这个数据结构，里面的成员包括一维数组，数组的容量，数组元素的个数，有两个直接后继。
堆的定义如下：n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时，称之为堆。
(且)或者(), ()
若将和此次序列对应的一维数组（即以一维数组作此序列的存储结构）看成是一个完全二叉树，则堆的含义表明，完全二叉树中所有非终端结点的值均不大于（或不小于）其左、右孩子结点的值。由此，若序列{k1,k2,…,kn}是堆，则堆顶元素（或完全二叉树的根）必为序列中n个元素的最小值（或最大值）。
在这里插入图片描述

将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等
堆的性质：

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

🌠 堆的实现

🌉堆向下调整算法

现在我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提：左右子树必须是一个堆，才能调整。

int array[] = {27,15,19,18,28,34,65,49,25,37};

在这里插入图片描述

void AdjustDown(HPDataType* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child+1<n && a[child + 1]>a[child])
		{
			child++;
		}
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

🌉堆的创建

下面我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。根节点左右子树不是堆，我们怎么调整呢？这里我们从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆。

int a[] = {1,5,3,8,7,6};

在这里插入图片描述

代码：

int size=sizeof(array)/sizeof(int);
//向下建堆，复杂度为O(N)
for (int i = (size - 1 - 1) / 2; i >= 0; i--)
{
	AdjustDown(array, size,i);
}
void AdjustDown(HPDataType* a, int n, int parent)
{ //a是数组指针,n是数组长度,parent是当前需要下调的父结点索引

	int child = parent * 2 + 1;
	//child表示父结点parent的左孩子结点索引,因为是完全二叉堆,可以通过parent和2计算得到

	while (child < n)
	{
		//如果左孩子存在

		if (child + 1 < n && a[child + 1] < a[child])
		{
			//如果右孩子也存在,并且右孩子值小于左孩子,则child指向右孩子
			child++;
		}
		if (a[child] < a[parent])
			//如果孩子结点值小于父结点值,则需要交换
		{
			Swap(&a[child], &a[parent]);
			//交换孩子和父结点
			parent = child;
			//父结点下移为当前孩子结点

			child = parent * 2 + 1;

			//重新计算新的左孩子结点索引

		}
		else
		{
			break;
		}
	}
}

这是向下调整，最终形成小根堆，如果你想修改大根堆只需改变两个代码方向即可：

if (child+1<n && a[child + 1]>a[child])
if (a[child] > a[parent])

🌉建堆时间复杂度

因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个节点不影响最终结果)：

复杂度：O(N)
在这里插入图片描述

🌉堆的插入

先插入一个10到数组的尾上，再进行向上调整算法，直到满足堆。

在这里插入图片描述

void HPPush(HP* php, HPDataType x)
{
	assert(php);

	if (php->size == php->capacity)
	{
		size_t newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType * tmp = realloc(php->a, sizeof(HPDataType) * newCapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		php->a = tmp;
		php->capacity = newCapacity;
	}

	php->a[php->size] = x;
	php->size++;

	AdjustUp(php->a, php->size - 1);
}

🌉堆的删除

删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。
在这里插入图片描述

//时间复杂度是：logN
void HPPop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	
	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;

	AdjustDown(php->a, php->size, 0);
}

🌠堆向上调整算法

堆向上调整算法主要用于堆排序中,删除堆顶元素后,将最后一个元素补至堆顶,然后需要向上调整。

//向上调整，建堆O(N*logN)
for (int i = 1; i < size; i++)
{ //for循环从索引1开始,到size结束,即从第二个元素开始。
	AdjustUp(array, i);
}
void AdjustUp(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;//计算父节点的位置:父节点位置 = (当前节点位置-1)/2
	while (child > 0)//如果当前节点位置大于0,并且当前节点值小于父节点值,需要向上调整:
	{
		if (a[parent] < a[child])
		{
			Swap(&a[parent], &a[child]);
			child = parent;
			parent = (parent - 1) / 2;
		}//将当前节点位置设为父节点的位置,重复执行步骤2和步骤3
		//直到当前节点位置为0,或者当前节点值不小于父节点值为止。
		else
		{
			break;
		}
	}
}

堆向上调整的主要步骤:：确定需要调整的子节点,通常是补至堆顶的最后一个元素。
时间复杂度为O(N*logN)
在这里插入图片描述

🌉堆的接口

# define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
#include<string.h>

typedef int HPDataType;

typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;

void Swap(int* px, int* py);
void AdjustUp(HPDataType* a, int child);
void AdjustDown(HPDataType* a, int n, int parent);


//堆的简单初始化
//void HPInit(HP* php);
//堆的初始化+建堆
void HPInitArray(HP* php, HPDataType* a, int n);
//堆的销毁
void HPDestroy(HP* php);
//堆插入数据然后保持数据是堆
void HPPush(HP* php, HPDataType x);
//取堆顶的数据
HPDataType HPTop(HP* php);
//删除堆数据
void HPPop(HP* php);
//堆的数据个数
int HeapSize(HP* php);
//堆的判空
bool HPEmpty(HP* php);

🌠堆的实现

#include"HeadSort.h"
//堆的简单初始化
void HPInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->size = 0;
	php->capacity = 0;
}

void HPInitArray(HP* php, HPDataType* a, int n)
{
	assert(php);

	php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
	if (php->a == NULL)
	{
		perror("malloc fail");
		return;
	}

	memcpy(php->a, a, sizeof(HPDataType) * n);
	php->capacity = php->size = n;
	//HPInitArray:

	/*初始化堆数组,并将数据拷贝过来
	有两种方式建堆:
	向上调整:每个节点都与父节点比较,时间复杂度O(NlogN)向下调整:
	从最后一个非叶子节点开	始,每个节点与子节点比较,时间复杂度O(N)
	这里采用向下建堆,复杂度更低*/
	//向上调整，建堆O(N*logN)
	/*for (int i = 1; i < php->size; i++)
	{
		AdjustUp(php->a, i);
	}*/

	//向下建堆，复杂度为O(N)
	for (int i = (php->size - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(php->a, php->size,i);
	}
}

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

void Swap(int* px, int* py)
{
	int temp = *px;
	*px = *py;
	*py = temp;
}

void AdjustUp(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[parent] > a[child])
		{
			Swap(&a[parent], &a[child]);
			child = parent;
			parent = (parent - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

void HPPush(HP* php, HPDataType x)
{
	assert(php);

	if (php->size == php->capacity)
	{
		size_t newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType * tmp = realloc(php->a, sizeof(HPDataType) * newCapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		php->a = tmp;
		php->capacity = newCapacity;
	}

	php->a[php->size] = x;
	php->size++;

	AdjustUp(php->a, php->size - 1);
}

HPDataType HPTop(HP* php)
{
	assert(php);
	return php->a[0];

}

void AdjustDown(HPDataType* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child+1<n && a[child + 1]<a[child])
		{
			child++;
		}
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

//时间复杂度是：logN
void HPPop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	
	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;

	AdjustDown(php->a, php->size, 0);
}

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


bool HPEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}

🌠堆的实现代码测试

int main()
{
	int a[] = { 60,70,65,50,32,100 };
	HP hp;
	HPInitArray(&hp, a, sizeof(a) / sizeof(int));

	/*HPInit(&hp);
	for (int i = 0; i < sizeof(a) / sizeof(int); i++)
	{                         
		HPPush(&hp, a[i]);
	}

	printf("%d\n", HPTop(&hp));
	HPPop(&hp);
	printf("%d\n", HPTop(&hp));*/

	while (!HPEmpty(&hp))
	{
		printf("%d\n", HPTop(&hp));
		HPPop(&hp);
	}

	HPDestroy(&hp);
	return 0;
}

在这里插入图片描述

🚩总结

感谢你的收看，如果文章有错误，可以指出，我不胜感激，让我们一起学习交流，如果文章可以给你一个小小帮助，可以给博主点一个小小的赞😘

请添加图片描述

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

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

相关文章

什么是资源子网和通信子网有什么特点

什么是资源子网和通信子网有什么特点

资源子网和通信子网是计算机网络中常见的两种子网类型&#xff0c;它们分别承担着资源管理和数据传输的重要功能。资源子网以共享资源为核心&#xff0c;通过集中管理和高效共享提高了资源利用率&#xff0c;而通信子网则负责连接不同资源子网&#xff0c;实现数据的传输和通信…
阅读更多...
Spring-1

Spring-1

目录 概念 优点 Autowired和Resource关键字 相同点 不同点 依赖注入的三种方式 概念 Spring 是个java企业级应用的开源开发框架。Spring主要用来开发Java应用&#xff0c;但是有些扩展是针对构建J2EE&#xff08;Java平台企业版&#xff09;平台的web应用。Spring 框架目…
阅读更多...
emment语法

emment语法

文章目录 1. 生成普通的标签2. 生成 div类名3. 生成指定标签类名/id 值4. 生成带有子元素的标签5. 生成内部文本6. 一次可以生成多个标签7. 生成带有指定属性 的元素8. 生成相邻兄弟元素 1. 生成普通的标签 本质使用的就是元素选择器&#xff0c;例如 div p a 标签等等。 2. …
阅读更多...
基于Benchmark查看OceanBase执行计划

基于Benchmark查看OceanBase执行计划

&#x1f4e2;&#x1f4e2;&#x1f4e2;&#x1f4e3;&#x1f4e3;&#x1f4e3; 哈喽&#xff01;大家好&#xff0c;我是【IT邦德】&#xff0c;江湖人称jeames007&#xff0c;10余年DBA及大数据工作经验 一位上进心十足的【大数据领域博主】&#xff01;&#x1f61c;&am…
阅读更多...
stm32-定时器输入捕获

stm32-定时器输入捕获

目录 一、输入捕获简介 二、输入捕获框图 1.定时器总框图 2.输入捕获框图 3.主从触发模式 三、固件库实现 1.定时器测量PWM频率 2.PWMI模式 一、输入捕获简介 二、输入捕获框图 1.定时器总框图 上图可知&#xff0c;四个输入捕获和输出比较共用4个CCR寄存器&#x…
阅读更多...
perl 用 XML::LibXML DOM 解析 Freeplane.mm文件，生成测试用例.csv文件

perl 用 XML::LibXML DOM 解析 Freeplane.mm文件，生成测试用例.csv文件

Freeplane 是一款基于 Java 的开源软件&#xff0c;继承 Freemind 的思维导图工具软件&#xff0c;它扩展了知识管理功能&#xff0c;在 Freemind 上增加了一些额外的功能&#xff0c;比如数学公式、节点属性面板等。 在云计算中&#xff0c;解析XML元素和属性是一种常见的操作…
阅读更多...
数据库 | MYSQL这个复杂系统如何上手？

数据库 | MYSQL这个复杂系统如何上手？

当你不知道从何入手研究或解决一个复杂系统的问题时&#xff0c;通常意味着你没有找到合适的切入点或者缺乏对系统整体和细节之间联系的理解。在这种情况下&#xff0c;一个有用的策略是寻找系统的基本原理或构成要素。 小时候&#xff0c;你可能也玩过玩具四驱车。有的四驱车…
阅读更多...
如何搭建“Docker Registry私有仓库，在CentOS7”？

如何搭建“Docker Registry私有仓库，在CentOS7”？

1、下载镜像Docker Registry docker pull registry:2.7.1 2、运行私有库Registry docker run -d -p 5000:5000 -v ${PWD}/registry:/var/lib/registry --restartalways --name registry registry:2.7.1 3、拉取镜像 docker pull busybox 4、打标签&#xff0c;修改IP&#x…
阅读更多...
气液分离器的选型介绍

气液分离器的选型介绍

气液分离器在热泵或制冷系统中的基本作用是分离出并保存回气管里的液体以防止压缩机液击。因此，它可以暂时储存多余的制冷剂液体，并且也防止了多余制冷剂流到压缩机曲轴箱造成油的稀释。因为在分离过程中，冷冻油也会被分离出来并积存在底部，所以在气液分离器出口管和底部会…
阅读更多...
Github 2024-03-16 Rust开源项目日报 Top10

Github 2024-03-16 Rust开源项目日报 Top10

根据Github Trendings的统计，今日(2024-03-16统计)共有10个项目上榜。根据开发语言中项目的数量，汇总情况如下： 开发语言项目数量Rust项目10TypeScript项目2Go项目1RustDesk: 用Rust编写的开源远程桌面软件 创建周期：1218 天开发语言：Rust, Dart协议类型：GNU Affero Gene…
阅读更多...
绝地求生：PUBG 2024年 更新重点偏向于武器平衡、游戏互动及联名道具

绝地求生：PUBG 2024年 更新重点偏向于武器平衡、游戏互动及联名道具

一、游戏体验 1. 增加可破坏的环境 1.1 增加更多互动功能 通过可破坏环境将游戏方式变得千变万化。待功能上线&#xff0c;在后续游戏中玩家可以对建筑物进行部分破坏来开辟新的进攻、撤退路线&#xff0c;或搭建掩体进行战略性攻击。 环境破坏部分功能&#xff0c;将会在4…
阅读更多...
“风口”上的量化大厂“绣球”抛向中低频人才

“风口”上的量化大厂“绣球”抛向中低频人才

量化人才这几年是人才舞台上的“香饽饽”。 遵循着低频不如高频、小厂不如大厂的薪资逻辑&#xff0c;各路人才被各路机构“哄抢”&#xff0c;薪资一路走高。 但2024年的“信号”再强烈不过——量化大厂们到了改变的时候了。 而量化大厂们显然对此已“心知肚明”....... “…
阅读更多...
19 OpenCV 霍夫曼变换检测圆

19 OpenCV 霍夫曼变换检测圆

文章目录 cv::HoughCircles算子参数示例 cv::HoughCircles 因为霍夫圆检测对噪声比较敏感&#xff0c;所以首先要对图像做中值滤波。 基于效率考虑&#xff0c;Opencv中实现的霍夫变换圆检测是基于图像梯度的实现&#xff0c;分为两步&#xff1a; 检测边缘&#xff0c;发现可能…
阅读更多...
深度学习 精选笔记（11）深度学习计算相关：GPU、参数、读写、块

深度学习 精选笔记（11）深度学习计算相关：GPU、参数、读写、块

学习参考&#xff1a; 动手学深度学习2.0Deep-Learning-with-TensorFlow-bookpytorchlightning ①如有冒犯、请联系侵删。 ②已写完的笔记文章会不定时一直修订修改(删、改、增)&#xff0c;以达到集多方教程的精华于一文的目的。 ③非常推荐上面&#xff08;学习参考&#x…
阅读更多...
oracle基础-子查询 备份

oracle基础-子查询 备份

一、什么是子查询 子查询是在SQL语句内的另外一条select语句&#xff0c;也被称为内查询活着内select语句。在select、insert、update、delete命令中允许是一个表达式的地方都可以包含子查询&#xff0c;子查询也可以包含在另一个子查询中。 【例1.1】在Scott模式下&#xff0…
阅读更多...
CSS扩展选择器

CSS扩展选择器

文章目录 1. 并集选择器2. 交集选择器3. 后代选择器4. 子代选择器5. 兄弟选择器5.1. 相邻兄弟选择器5.2. 通用兄弟选择器 6. 属性选择器7. 伪类选择器7.1. 动态伪类7.2. 结构伪类7.3. 否定伪类 8. 伪元素选择器9. Google 改进案例 1. 并集选择器 选中多个选择器对应的元素。一…
阅读更多...
如何在Linux上使用git远程上传至gitee托管（add-commit-push指令详解）

如何在Linux上使用git远程上传至gitee托管（add-commit-push指令详解）

&#x1f490; &#x1f338; &#x1f337; &#x1f340; &#x1f339; &#x1f33b; &#x1f33a; &#x1f341; &#x1f343; &#x1f342; &#x1f33f; &#x1f344;&#x1f35d; &#x1f35b; &#x1f364; &#x1f4c3;个人主页 &#xff1a;阿然成长日记 …
阅读更多...
Xpay源支付2.8.8免授权聚合免签系统

Xpay源支付2.8.8免授权聚合免签系统

产品介绍 XPay是专为个人站长打造的聚合免签系统&#xff0c;拥有卓越的性能和丰富的功能。采用全新轻量化的界面UI&#xff0c;让您可以更加方便快捷地解决知识付费和运营赞助的难题。同时&#xff0c;它基于高性能的ThinkPHP 6.1.2 Layui 2.8.10 PearAdmin架构&#xff0c…
阅读更多...
面向对象（下）

面向对象（下）

目录 01、static1.1、static的使用1.2、static应用举例1.3、单例(Singleton)设计模式 02、main方法的语法03、类的成员之四&#xff1a;代码块04、关键字&#xff1a;final05、抽象类与抽象方法5.1、多态的应用&#xff1a;模板方法设计模式(TemplateMethod) 06、接口(interfac…
阅读更多...
使用reprepro+nginx搭建apt服务器

使用reprepro+nginx搭建apt服务器

目录 项目背景 项目要求 项目开发过程 1、apt服务器的搭建 2、实现自定义指定源文件列表来实现apt update更新 3、实现软件启动时自动更新 4. source.list中镜像源地址的格式 项目开发的难点/坑点 总结 项目背景 前面写过一篇“利用Nginx搭建一个apt服务器”&#xff…
阅读更多...
最新文章

Copyright @ 2022~2023