堆（二叉树，带图详解）

一.堆

1.堆的概念

2.堆的存储方式

逻辑结构

 物理结构

2.堆的插入问题

3.堆的基本实现（代码）（以小堆为例）

1.堆的初始化

2. 向上调整

 3.插入结点

4. 交换函数、堆的打印

5.向下调整

 6.删除根节点并调整成小根堆

7.获取堆顶的元素

8.判断栈是否为空

9.另一种初始化数组的方法

10.两种实现堆排序的方法的比较

二、堆的应用与实现

1.堆的升序写法

 升序堆：

2.向下调整建堆(大堆)

总结

🗡CSDN主页：d1ff1cult.🗡

🗡代码云仓库：d1ff1cult.🗡

🗡文章栏目：数据结构专栏🗡

一.堆

1.堆的概念

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

堆是一种非线性结构，是完全二叉树

堆分为小根堆（小堆）和大根堆（大堆）两种，小堆中所有的父节点均小于他的子结点，大堆中所有的父结点均大于子节点。

堆的底层用数组存储

小根堆：

大根堆：

顺序存储下左右子树与父节点之间的关系：
leftchild=parent*2+1；

rightchild=parent*2+2；

parent=（child-1）/2;

2.堆的存储方式

🗡逻辑结构

这里的逻辑结构是我们为了可以更好的李姐而想象出来的

 🗡物理结构

堆在内存中就是这样存储的

2.堆的插入问题

插入90我们发现该堆仍然是小堆，其实这是一个巧合，当我们插入50的时候发现该堆不再是一个小堆，我们此时需要不断地对50进行调整才能使得该堆重新成为小堆。

接下来继续向堆中插入一个5

插入数据后调整的基本思路:此时5的下标为6，根据5的下标找到5的父亲结点（5-1）/2=2 ，5的父亲结点为56，再让5与56比较大小，发现56>5所以将56和5的位置进行交换，再继续让交换后的5找父亲节点，5的父亲结点的下标为（2-1）/2=0，5的父亲结点为10，再将5与10继续比较，10>5进行交换，此时5的下标为0为根节点，调整完毕。

第一次进行交换:56与5进行比较 5<56 交换5和56

第二次进行交换： 找到交换后的5的父节点10，将10与5进行比较5<10则交换5与10的位置

 

很奇怪，这个最后插入的5 从孙子一跃成为了爷爷（bushi

3.堆的基本实现（代码）（以小堆为例）

下面介绍几个主要的实现堆的函数。

typedef int HPDataType;

typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;
void Swap(HPDataType* a, HPDataType* b);
void HeapPrint(HP* php);
void HeapInit(HP* php);
void HeapDestroy(HP* php);
void HeapPush(HP* php, HPDataType x);
void HeapPop(HP* php);
HPDataType HeapTop(HP* php);
void AdjustUp(HPDataType* a, int child);
void AdjustDown(HPDataType* a,int n,int parent);
bool HeapEmpty(HP* php);
void HeapInitArray(HP* php, int* a, int n);
void HeapSor

🗡堆的初始化

将数组和容量以及数组大小全部置空。

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

🗡向上调整

将插入的结点一步步调整，使该堆再次成为小堆

向上调整的前提：前面的数据是堆

AdjustUp(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;
	while (child>0)
	{
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (parent - 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");
		}
		php->a = tmp;
		php->capacity = newcapacity;
	}
	php->a[php->size] = x;
	php->size++;
	AdjustUp(php->a, php->size-1);
}

🗡交换函数、堆的打印

void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}//交换函数
void HeapPrint(HP* php)
{
	assert(php);
	for (int i = 0; i < php->size; i++)
	{
		printf("%d ", php->a[i]);
	}
	printf("\n");
}//堆的打印函数

🗡向下调整

向下调整的前提：根结点左右子树都是堆

void AdjustDown(HPDataType* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while(child<n)
	{
		if (child+1<n&&a[child] > a[child + 1])//保证child存的是左右孩子里面较小的那一个
		{
			++child;
		}

		if (a[child] < a[parent])// 父节点与两个儿子中较小的一个交换位置
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = child * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

🗡删除根节点并调整成小根堆

void HeapPop(HP* php)
{
	assert(php);  
	assert(php->size > 0);
	Swap(&php->a[0], php->a[php->size - 1]);
	--php->size;
	AdjustDowm(php->a, php->size, 0);
}

🗡获取堆顶的元素

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

🗡判断栈是否为空

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

🗡另一种初始化数组的方法

 void HeapInitArray(HP* php, int* a, int n)
 {
	 assert(php);
	 assert(a);
	 php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
	 if (php->a == NULL)
	 {
		 perror("malloc fail");
		 exit(-1);
	 }
	 php->size = n;
	 php->capacity = n;
	 memcpy(php->a, a, sizeof(HPDataType) * n); 
	 for (int i = 0; i < n; i++)
	 {
		 AdjustUp(php->a, i);
	 }
 }

🗡两种实现堆排序的方法的比较

 下面是使用HeapPush()函数实现堆排的过程  ：

void AdjustUp(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;
	while (child>0)
	{
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (parent - 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");
		}
		php->a = tmp;
		php->capacity = newcapacity;
	}
	php->a[php->size] = x;
	php->size++;
	AdjustUp(php->a, php->size-1);
}

这种方法是通过malloc函数开辟一块一块的空间，并通过不断地扩容将数据push到数组中，再对数组中的内容进行不断的向上调整从而达到堆排的目的。

下面是用AdjustUp()函数实现堆排的过程：

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

这种方法与HeapPush函数不同的地方在于该函数传参数时直接传入一个数组，省去了malloc开辟空间的消耗。

二、堆的应用与实现

🗡堆的升序写法

通常这里我们都会问一个问题，实现升序排序我们应该建一个小堆还是一个大堆？

答案是，升序时我们应该建一个大堆，那么为什么呢？

我们都知道小堆的根节点是整棵二叉树中最小的值，选出了最小的值之后，我们还要去找次小的值

 首先是建小堆不适用的原因，这里有这样一个数组，我们将这个数组展开：

 

 按照我们需要建升序堆的要求，我们会将最小的根节点删除掉，删除后如下图所示

我们发现这个二叉树不再是堆，但是我们要选择次小值的话需要进行调整，就需要重新建堆，建堆的时间复杂度为o(n)=n*logn,代价还是比较大的，甚至不如遍历一遍来的快，所以我们这里摒弃了建小堆的想法，那么接下来就看看建大堆的优势在哪里了

 建大堆的基本思想以及优势:

我们排升序，建一个大堆，将根节点和最后一个结点交换位置，那么最大的数就被交换到了数组的最后面，此时一个数字已经排好了，原本根节点的左右子树还是堆，我们就可以通过向下调整，来找出次打的值，此时我们不再把交换到数组最后的根节点看作树的结点，对剩下的数字进行向下调整，找出了次小的值，这里的时间复杂度O(n)仅仅为logn合计起来n个结点的时间复杂度O(n)=n*logn，消耗比较小。再与树的最后一个结点进行交换。过程我们用下面的数组进行演示。

 

将根节点的数字与树的最后一个结点的数字进行交换，并不再把交换到后面的根节点看作树的内容

 🗡升序堆：
void AdjustUp(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;
	while (child>0)
	{
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (parent - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
void AdjustDown(HPDataType* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while(child<n)
	{
		if (child+1<n&&a[child] > a[child + 1])//保证child存的是左右孩子里面较小的那一个
		{
			++child;
		}

		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = child * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void HeapSort(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		AdjustUp(a, i);
	}
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		--end;
	}
}

🗡向下调整建堆(大堆)

有这样一个数组，我们如果想通过用根节点直接向下调整建大堆，就必须保证根节点的左右子树都是大堆，所以我们就想出了倒着调整树的方法：

需要注意的是：单个叶子结点，既是大堆也是小堆。

这种建堆方法是从树的末尾开始找到第一个非叶子结点然后对其进行向下调整，从数组后面查找的第一个非叶子结点也就是树中最后一个结点的父节点，最后一个结点的下标为n-1，则它的父结点的下标为(n-1-1)/2 ，这棵树从后面查找的第一个非叶子结点是6，对6进行向下调整，如下图

我们发现调整完成之后，结点5的左子树已经成为了大堆，右子树也是大堆，那我们就应该对下一个非叶子结点进行调整了，我们只需要将60位置的下标+1，就得到了下一个非叶子结点的下标，同理也对他进行调整，直到2的左右子树都调整为大堆

void AdjustDown(HPDataType* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while(child<n)
	{
		if (child+1<n&&a[child] > a[child + 1])//保证child存的是左右孩子里面较小的那一个
		{
			++child;
		}

		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = child * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void HeapSort(int* a, int n)
{
	//向上调整建堆（大堆或者小堆）
	//for (int i = 0; i < n; i++)
	//{
	//	AdjustUp(a, i);
	//}
	//向下调整建堆
	for (int i = (n - 2) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		--end;
	}
}

向上调整建堆，时间复杂度O(n)=n*logn，而向下调整建堆的时间复杂度O(n)=n.

总结

上述就是关于堆的一些知识，有不懂的地方欢迎提问。

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

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

相关文章

【Javascrpt】比较，逻辑运算符

【Javascrpt】比较，逻辑运算符

目录 比较运算符 逻辑运算符 &&(与&#xff09; ||&#xff08;或&#xff09; 两真&#xff08;||左侧为真&#xff0c;||右侧为真&#xff09; 两假&#xff08;||左侧为假&#xff0c;右侧为假&#xff09; 一真一假&#xff08;||一侧为假&#xff0c;另一侧为…
阅读更多...
异常的处理和HTTP状态码的分类

异常的处理和HTTP状态码的分类

在爬虫过程中&#xff0c;可能会遇到各种异常情况&#xff0c;如网络连接错误、网页解析错误、请求超时等。为了提高爬虫的稳定性和容错性&#xff0c;需要对这些异常进行处理。 异常处理是通过捕获和处理异常来解决程序中出现的错误情况。在爬虫中&#xff0c;常见的异常处理…
阅读更多...
腾讯地图基本使用(撒点位,点位点击,弹框等...功能) 搭配Vue3

腾讯地图基本使用(撒点位,点位点击,弹框等...功能) 搭配Vue3

腾讯地图的基础注册账号 展示地图等基础功能在专栏的上一篇内容 大家有兴趣可以去看一看 今天说的是腾讯地图的在稍微一点的基础操作 话不多说 直接上代码 var marker ref(null) var map var center ref(null) // 地图初始化 const initMap () > {//定义地图中心点坐标…
阅读更多...
java中按行读取文件内容

java中按行读取文件内容

java中按行来读取文件内容&#xff0c;一般对文件也是又要求的&#xff0c;比如文件编码utf-8&#xff0c;内容是按行可读&#xff0c;而不是一堆字节码。这类文件&#xff0c;我们按行读取&#xff0c;主要是方便快速查看内容&#xff0c;并且用这些内容来作别的用途&#xff…
阅读更多...
如何解决找不到xinput1_3.dll无法继续执行此代码？5个解决方法分享

如何解决找不到xinput1_3.dll无法继续执行此代码？5个解决方法分享

由于各种原因&#xff0c;电脑可能会出现一些问题&#xff0c;其中之一就是电脑提示找不到xinput1_3.dll。这个问题可能会导致一些应用程序无法正常运行&#xff0c;给用户带来困扰。那么&#xff0c;当遇到这个问题时&#xff0c;我们应该如何修复呢&#xff1f;小编将详细介绍…
阅读更多...
华为防火墙双机热备拓扑

华为防火墙双机热备拓扑

阅读更多...
【算法训练-动态规划 五】【二维DP问题】最大正方形

【算法训练-动态规划 五】【二维DP问题】最大正方形

废话不多说&#xff0c;喊一句号子鼓励自己&#xff1a;程序员永不失业&#xff0c;程序员走向架构&#xff01;本篇Blog的主题是【动态规划】&#xff0c;使用【数组】这个基本的数据结构来实现&#xff0c;这个高频题的站点是&#xff1a;CodeTop&#xff0c;筛选条件为&…
阅读更多...
DNS、ICMP和NAT

DNS、ICMP和NAT

DNS、ICMP和NAT 文章目录 DNS、ICMP和NATDNS是什么域名系统的名字空间域名空间的层次结构域名的分配和管理顶级类别域名 DNS域名解析过程递归查询迭代查询 高速缓存 ICMPICMP的定位ICMP协议的功能 ICMP的报文格式ping命令traceroute命令 NATNAT技术背景NAT IP转换过程NAPTNAT的…
阅读更多...
云原生Docker Cgroups资源控制操作

云原生Docker Cgroups资源控制操作

目录 资源控制 cgroups四大功能 CPU 资源控制 设置CPU使用率上限 进行CPU压力测试 设置50%的比例分配CPU使用时间上限 设置CPU资源占用比&#xff08;设置多个容器时才有效&#xff09; 设置容器绑定指定的CPU 对内存使用的限制 限制容器可以使用的最大内存 限制可用的…
阅读更多...
“编辑微信小程序与后台数据交互与微信小程序wxs的使用“

“编辑微信小程序与后台数据交互与微信小程序wxs的使用“

引言 在现代移动应用开发中&#xff0c;微信小程序已经成为了一个非常流行和广泛使用的平台。为了使小程序能够展示丰富的内容和实现复杂的功能&#xff0c;与后台数据的交互是至关重要的。同时&#xff0c;微信小程序还提供了一种特殊的脚本语言——wxs&#xff0c;用于增强小…
阅读更多...
20231024后端研发面经整理

20231024后端研发面经整理

1.如何在单链表O(1)删除节点&#xff1f; 狸猫换太子 2.redis中的key如何找到对应的内存位置&#xff1f; 哈希碰撞的话用链表存 3.线性探测哈希法的插入&#xff0c;查找和删除 插入&#xff1a;一个个挨着后面找&#xff0c;知道有空位 查找&#xff1a;一个个挨着后面找…
阅读更多...
LeetCode 209. 长度最小的子数组

LeetCode 209. 长度最小的子数组

长度最小的子数组 题目链接 209. 长度最小的子数组 给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl1, ..., numsr-1, numsr] &#xff0c;并返回其长度**。**如果不存在符合条件的子数组&…
阅读更多...
【刷题-PTA】堆栈模拟队列(代码+动态图解)

【刷题-PTA】堆栈模拟队列(代码+动态图解)

【刷题-PTA】堆栈模拟队列(代码动态图解) 文章目录 【刷题-PTA】堆栈模拟队列(代码动态图解)题目输入格式:输出格式:输入样例:输出样例: 分析题目区分两栈解题思路伪代码动图演示代码测试 题目 题目描述 : 设已知有两个堆栈S1和S2&#xff0c;请用这两个堆栈模拟出一个队列Q。 …
阅读更多...
【数据结构】线性表（十）队列：循环队列及其基本操作（初始化、判空、判满、入队、出队、存取队首元素）

【数据结构】线性表（十）队列：循环队列及其基本操作（初始化、判空、判满、入队、出队、存取队首元素）

文章目录 队列1. 定义2. 基本操作 顺序队列循环队列1. 头文件和常量2. 队列结构体3. 队列的初始化4. 判断队列是否为空5. 判断队列是否已满6. 入队7. 出队8. 存取队首元素9. 获取队列中元素个数10. 打印队列中的元素9. 主函数10. 代码整合 堆栈Stack 和 队列Queue是两种非常重要…
阅读更多...
虚拟机VMware Workstation Pro安装配置使用服务器系统ubuntu-22.04.3-live-server-amd64.iso

虚拟机VMware Workstation Pro安装配置使用服务器系统ubuntu-22.04.3-live-server-amd64.iso

虚拟机里安装ubuntu-23.04-beta-desktop-amd64开启SSH(换源和备份)配置中文以及中文输入法等 ​一、获取Ubuntu服务器版 获取Ubuntu服务器版 二、配置虚拟机 选择Custom(advanced)&#xff1a; 选择Workstation 17.x: 选择“I will install the operating system later.”…
阅读更多...
I/O设备的概念和分类，I/O控制器

I/O设备的概念和分类，I/O控制器

文章目录 1.什么是I/O设备2.按使用特性分类1.人机交互类外部设备2.存储设备3.网络通信设备 3.按传输速率分类1.低速设备:2.中速设备:3.高速设备: 4.按信息交换的单位分类1.块设备:2.字符设备: 5.I/O设备的机械部件6.I/O设备的电子部件&#xff08;I/O控制器&#xff09;1.接收和…
阅读更多...
Vue中的加密方式（js-base64、crypto-js、jsencrypt、bcryptjs）

Vue中的加密方式（js-base64、crypto-js、jsencrypt、bcryptjs）

目录 1.安装js-base64库 2. 在Vue组件中引入js-base64库 3.使用js-base64库进行加密 4.Vue中其他加密方式 1.crypto-js 2.jsencrypt 3.bcryptjs 1.安装js-base64库 npm install js-base64 --save-dev 2. 在Vue组件中引入js-base64库 import { Base64 } from js-ba…
阅读更多...
快速排序(c语言代码实现)

快速排序(c语言代码实现)

交换排序&#xff1a;快速排序&#xff08;不稳定的排序&#xff09; 快速排序&#xff08;Quick Sort&#xff09;是一种常见的排序算法&#xff0c;它采用分治法的思想&#xff0c;对待排序序列进行划分&#xff0c;使得划分出的子序列可以分别进行排序&#xff0c;最终使整…
阅读更多...
2、Linux权限理解

2、Linux权限理解

个人主页&#xff1a;Lei宝啊 愿所有美好如期而遇 目录 前言 Linux权限的概念 1.文件访问者的分(人) 2.文件类型和访问权限(事物属性) 3.文件权限值的表示方法 4.文件访问权限的相关设置方法 file指令 目录的权限 粘滞位 关于权限的总结 前言 在开始Linux权限理…
阅读更多...
python二次开发Solidworks：读取样条曲线数据

python二次开发Solidworks：读取样条曲线数据

目录 1、草图段对象 2、VBA代码分析 3、python代码实现 样条曲线&#xff08;spline curve&#xff09;是数学术语&#xff0c;是一种特殊的参数曲线&#xff0c;由一组控制点通过曲线拟合的方式生成。样条一词源于船舶建造中的一种临时性辅助支架&#xff0c;后来被引入计算…
阅读更多...
最新文章

Copyright @ 2022~2023