当前位置： 首页 > article >正文

【数据结构】树-二叉树-堆(下)

article 2024/11/5 18:46:36


🍃 如果觉得本系列文章内容还不错，欢迎订阅🚩
🎊个人主页:小编的个人主页
🎀 🎉欢迎大家点赞👍收藏⭐文章
✌️ 🤞 🤟 🤘 🤙 👈 👉 👆 🖕 👇 ☝️ 👍

目录

  • 🐼前言
  • 🐼堆
  • 🐼初始化堆
  • 🐼堆的销毁
  • 🐼堆的插入
  • 🐼向上调整算法
  • 🐼堆的判空
  • 🐼 堆的删除
  • 🐼向下调整算法
  • 🐼取堆顶的数据
  • 🐼堆的数据个数
  • 🐼全部源码
  • 🐼文末

🐼前言

🌟在上一节我们介绍了二叉树的相关概念，如果感兴趣的小伙伴，可以阅读我的上一篇文章:> 树-二叉树-堆，这一节我们介绍一种特殊的二叉树：堆

🐼堆

✨ 堆的概念
一般使用顺序结构的二叉树称之为堆，堆是一种特殊的二叉树，不仅具有二叉树的特性，还具有其他的特性。
😃如果有⼀个关键码的集合 K = {k0 , k1 , k2 , …，kn−1 } ，把它的所有元素按完全⼆叉树的顺序存储方式存储，在⼀个⼀维数组中，并满足： Ki <= K2∗i+1 （ Ki >=K2∗i+1 且 Ki <= K2∗i+2 ），i = 0、1、2… ，则称为堆(或大堆)。将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆。

🐋小根堆
在这里插入图片描述🐋大根堆
在这里插入图片描述

🐾现在我们来讨论二叉树的性质:
对于具有 n 个结点的完全二叉树，如果按照从上到下从左到右的数组顺序对所有结点从0 开始编号，则对于序号为 i 的结点有：
如果i>0,那么双亲节点序号: (i-1)/2 ;
i=0,为根节点，无双亲节点。
如果2i+1<n;左孩子节点: 2i+1
如果2i+2<n右孩子节点:2i+2

✨我们既然知道堆是基于数组来实现的。那和我们之前实现的顺序表，栈一样:现在我们来定义堆的结构:

typedef	int HPDataType;
typedef struct Heap
{
	HPDataType* arr;
	int size;
	int capacity;
}Hp;

以下是堆常见方法的实现以及解析:

🐼初始化堆

//初始化堆
void HeapInit(Hp* php)
{
	assert(php);
	php->arr = NULL;
	php->size = php->capacity = 0;
}

🌻代码解析

✨ 我们将还未开辟的数组指针置为空，并将堆中有效元素个数和容量大小置为0。
时间复杂度为O(1),程序执行常数次，空间复杂度为O(1),只创建有效个变量

🐼堆的销毁

// 堆的销毁
void HeapDestory(Hp* php)
{
	assert(php);
	if (php->arr)
		free(php->arr);
	php->arr = NULL;
	php->size = php->capacity = 0;
}

🌻代码解析

✨ 如果指向堆数组的空间存在，释放指向数组的那块空间，并将其置为NULL，防止野指针的发生。最后重置size和capacity
时间复杂度为O(1),程序执行常数次，空间复杂度为O(1),只创建有效个变量

🐼堆的插入

/ 堆的插入
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->arr, newcapacity * sizeof(HPDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		php->arr = tmp;
		php->capacity = newcapacity;
	}
	php->arr[php->size] = x;
	//尾部插入.向上调整
	AdjustUp(php->arr, php->size);
	++php->size;
}

🌻代码解析

✨ 向堆内插入元素默认是在尾部插入元素。首先要检查堆是否为空，如果为空，那么就要通过realloc进行增容操作，并更新capacity。将要插入的元素插入。因为是堆结构，每插入一个元素就需要对堆进行重新排序。所以这里封装了一个AdjustUp函数，这个函数用于调整堆值的关系，目的是，如果插入一个元素，是大根堆，结果还是大根堆，是小根堆，结果还是小根堆。
🍀测试结果:
在这里插入图片描述

下面来探讨向上调整算法的实现。

🐼向上调整算法

//向上调整
void AdjustUp(HPDataType* arr, int child)
{
	int parent = (child - 1) / 2;
	//建小堆
	while (child > 0)
	{
		//<小堆
		//>大堆
		if (arr[child] < arr[parent] )
		{
			Swap(&arr[child], &arr[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

🌻代码解析

✨ 我们调整参数的是堆数组，所以用arr接收，以及插入的孩子节点。
在上面二叉树的性质我们得知，已知孩子节点,则父节点是:parent = (child-1)/2，这里我们如果建小堆，即孩子节点要大于双亲节点的，不满足，则进行交换，并接着让child走到parent,parent再走到parent的父节点。如果已经满足，则跳出循坏。
🍂画图剖析:
在这里插入图片描述
如上图，每次在堆尾节点插入元素，需要向上调整，重新建堆

🚗这里来详细说明向上调整算法的时间复杂度:
因为堆是完全二叉树，这里近似看做满二叉树，对时间复杂度没有影响。
分析：
第1层， 2^0 个结点，需要向上移动0层.
第2层， 2^1 个结点，需要向上移动1层.
第3层， 2^2 个结点，需要向上移动2层.
第4层， 2^3 个结点，需要向上移动3层.
…
第h层， 2^(h-1) 个结点，需要向上移动h-1层.
则需要移动结点总的移动步数为：每层结点个数 * 向上调整次数（第⼀层调整次数为0）
在这里插入图片描述

🐼堆的判空

// 堆的判空
bool HeapEmpty(Hp* php)
{
	assert(php);
	return php->size == 0;
}

🌻代码解析

✨ 通过堆中有效元素的个数直接返回布尔值。
时间复杂度为O(1),程序执行常数次，空间复杂度为O(1),只创建有效个变量

🐼 堆的删除

void HeapPop(Hp* php)
{
	assert(!HeapEmpty(php));
	//交换第一个和最后一个元素
	Swap(&php->arr[0], &php->arr[php->size - 1]);
	php->size--;
	//向下调整
	AdjustDown(php->arr, 0,php->size);
}

🌻代码解析

✨ 删除堆中的数据，指的是删除堆头的数据。删除堆头，不能直接将堆头删除，这样就破坏了堆结构，而是通过将要删除的第一个元素和最后一个元素互相交换位置。不过这样又会打乱堆，此时我们有需要再次调整堆，将堆调整成有序堆。

下面我们介绍令一种调整算法:向下调整算法。

🐼向下调整算法

//向下调整
void AdjustDown(HPDataType* arr, int parent, int n)
{
	HPDataType child = parent * 2 + 1;
	
	while (child < n)
	{
		//找最小的孩子--小堆
		//找最大的孩子--大堆
		
		if (arr[child] < arr[child + 1] && child+1<n)
		{
			child++;
		}
		//<小堆
		//>大堆
		if (arr[child] > arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

🌻代码解析

✨ 首先，向下调整的还是堆数组，传过来的初始都是根节点，堆中有效元素个数是n。
📝向下调整算法:
将堆顶元素与堆中最后一个元素进行交换
• 删除堆中最后⼀个元素
• 将堆顶元素向下调整到满足堆特性为止。
🍏传过来的是父节点，所以先找到孩子节点child。我们上面已知双亲节点，求孩子节点:child =parent * 2 + 1; 。这里如果建小堆，要先找到孩子节点中较小的孩子(child)，再与双亲节点(parent)交换，注意，右孩子(child)也要小于节点个数，接着，如果较小的孩子(child)小于双亲节点(parent)，交换较小的孩子(child)和双亲节点(parent)保存的值，再让双亲节点(parent)走到孩子节点(child)，再更新孩子节点，否则，直接，跳出循环。child最多不能超过有效节点个数n作为循环条件.

🍂画图剖析:
在这里插入图片描述

🚗这里来详细说明向下调整算法的时间复杂度
分析：
第1层， 2^0 个结点，需要向下移动h-1层.
第2层， 2^1 个结点，需要向下移动h-2层.
第3层， 2^2 个结点，需要向下移动h-3层.
第4层， 2^3 个结点，需要向下移动h-4层.
…
第h-1层， 2^(h-2) 个结点，需要向下移动1层.
则需要移动结点总的移动步数为：每层结点个数 * 向上调整次数（第⼀层调整次数为0）
在这里插入图片描述
总结，堆的向上调整算法和向下调整算法都既可以建大堆也可以建小堆。向上调整算法主要是堆的插入。而向下调整算法用于建堆和堆排序。这里能看出,向下调整算法时间复杂度比向上调整算法更优

测试结果同下面取堆顶的数据一起展示。

🐼取堆顶的数据

// 取堆顶的数据
HPDataType HeapTop(Hp* php)
{
	assert(!HeapEmpty(php));
	return php->arr[0];
}

🌻代码解析
✨ 堆不为空才可以取元素。将堆顶元素返回。
时间复杂度为O(1),程序执行常数次，空间复杂度为O(1),只创建有效个变量
🍀测试结果:
在这里插入图片描述

🐼堆的数据个数

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

🌻代码解析

✨直接返回堆中有效元素个数
时间复杂度为O(1),程序执行常数次，空间复杂度为O(1),只创建有效个变量

🐼全部源码

Heap.h

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

typedef	int HPDataType;

typedef struct Heap
{
	HPDataType* arr;
	int size;
	int capacity;
}Hp;

//初始化堆
void HeapInit(Hp* php);
// 堆的销毁
void HeapDestory(Hp* php);
// 堆的插入//尾部插入
void HeapPush(Hp* php, HPDataType x);
// 堆的删除//头部删除
void HeapPop(Hp* php);
// 取堆顶的数据
HPDataType HeapTop(Hp* php);
// 堆的数据个数
int HeapSize(Hp* php);
// 堆的判空
bool HeapEmpty(Hp* php);
//交换
void Swap(HPDataType* x, HPDataType* y);

//向下调整
void AdjustDown(HPDataType* arr, int parent, int n);
//向上调整
void AdjustUp(HPDataType* arr, int child);

Heap.c

#include "Heap.h"

//初始化堆
void HeapInit(Hp* php)
{
	assert(php);
	php->arr = NULL;
	php->size = php->capacity = 0;
}

// 堆的销毁
void HeapDestory(Hp* php)
{
	assert(php);
	if (php->arr)
		free(php->arr);
	php->arr = NULL;
	php->size = php->capacity = 0;
}

void Swap(HPDataType* x, HPDataType* y)
{
	HPDataType tmp = *x;
	*x = *y;
	*y = tmp;
}
//向上调整
void AdjustUp(HPDataType* arr, int child)
{
	int parent = (child - 1) / 2;
	//建小堆
	while (child > 0)
	{
		//<小堆
		//>大堆
		if (arr[child] < arr[parent] )
		{
			Swap(&arr[child], &arr[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

//向下调整
void AdjustDown(HPDataType* arr, int parent, int n)
{
	HPDataType child = parent * 2 + 1;
	
	while (child < n)
	{
		//找最小的孩子--小堆
		//找最大的孩子--大堆
		
		if (arr[child] < arr[child + 1] && child+1<n)
		{
			child++;
		}
		//<小堆
		//>大堆
		if (arr[child] > arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		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->arr, newcapacity * sizeof(HPDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		php->arr = tmp;
		php->capacity = newcapacity;
	}
	php->arr[php->size] = x;
	//尾部插入.向上调整
	AdjustUp(php->arr, php->size);
	++php->size;
}

// 堆的判空
bool HeapEmpty(Hp* php)
{
	assert(php);
	return php->size == 0;
}
// 堆的删除
void HeapPop(Hp* php)
{
	assert(!HeapEmpty(php));
	//交换第一个和最后一个元素
	Swap(&php->arr[0], &php->arr[php->size - 1]);
	php->size--;
	//向下调整
	AdjustDown(php->arr, 0,php->size);
}


// 取堆顶的数据
HPDataType HeapTop(Hp* php)
{
	assert(!HeapEmpty(php));
	return php->arr[0];
}
// 堆的数据个数
int HeapSize(Hp* php)
{
	assert(php);
	return php->size;
}

test.c

void test()
{
	Hp hp;
	HeapInit(&hp);
	//堆的插入
	HeapPush(&hp, 8);
	HeapPush(&hp, 14);
	HeapPush(&hp, 6);
	HeapPush(&hp, 17);
	//堆的删除
	/*HeapPop(&hp);
	HeapPop(&hp);
	HeapPop(&hp);
	HeapPop(&hp);*/
	while (!HeapEmpty(&hp))
	{
		printf("%d ", HeapTop(&hp));
		HeapPop(&hp);
	}
	HeapDestory(&hp);
}

🐼文末

感谢你看到这里，如果觉得本篇文章对你有帮助，点个赞👍 吧，你的点赞就是我更新的最大动力 ⛅️🌈 ☀️


http://www.kler.cn/a/377635.html

相关文章：

  • 一二三应用开发平台自定义查询设计与实现系列3——通用化重构
  • 【ACM出版，EI稳定检索，九大高校联合举办, IEEE Fellow支持】2024年计算机视觉与艺术研讨会（CVA 2024，11月29-12月1日）
  • 人工智能原理实验一：知识的表示与推理实验
  • 显存占用 显存测试
  • Linux中使用NGINX
  • 【Java知识】Java基础-对象排序的实现
  • 本地部署bert-base-chinese模型交互式问答，gradio
  • IDEA设置语法高亮自动检查xml中sql语法
  • Android13开发恢复出厂设置默认打开WiFi
  • 基于SSM+微信小程序的订餐管理系统（点餐2）
  • [算法初阶]第二集 滑动窗口
  • Google“Big Sleep“人工智能项目发现真实软件漏洞
  • 【算法赌场】区间合并
  • 传递悄悄话
  • java8有哪些新特性
  • 盘点谷歌全家桶中最值得付费的服务
  • 基于STL的自定义栈与队列实现：灵活选择底层容器的模板设计
  • 长度最小的子数组（滑动窗口）
  • cangjie仓颉程序设计-数据结构（四）
  • 无人机之远程指挥中心技术篇
  • 鸿蒙中的FA模型和Stage模型
  • 10.31.2024刷华为OD C题型
  • Scikit-learn和Keras简介
  • 为啥学习数据结构和算法
  • 最新整理：linux常见面试题库
  • 代码源NOIP DAY2 T1 LIS和LDS题解