【数据结构】堆详解!(图解+源码)

这篇具有很好参考价值的文章主要介绍了【数据结构】堆详解!(图解+源码)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

堆内存数据结构,数据结构探索,数据结构,堆,c语言,开发语言,算法
🎥 屿小夏 : 个人主页
🔥个人专栏 : 数据结构解析
🌄 莫道桑榆晚,为霞尚满天!

堆内存数据结构,数据结构探索,数据结构,堆,c语言,开发语言,算法

🌤️前言

堆是一种基本而强大的数据结构。本文将深入探讨堆的概念、原理以及实现。

🌤️堆的理论

☁️二叉树的顺序存储

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

堆内存数据结构,数据结构探索,数据结构,堆,c语言,开发语言,算法

☁️堆的概念

堆内存数据结构,数据结构探索,数据结构,堆,c语言,开发语言,算法

堆的性质:

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

堆内存数据结构,数据结构探索,数据结构,堆,c语言,开发语言,算法

🌤️堆的实现逻辑

☁️堆向下调整算法

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

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

堆内存数据结构,数据结构探索,数据结构,堆,c语言,开发语言,算法

☁️建堆

给定一个数组,这个数组逻辑上可以看做一颗完全二叉树,但是还不是一个堆,这个时候就需要我们通过算法,把它构建成一个堆。根节点左右子树不是堆,我们从倒数的第一个非叶子节点的子树开始调整,一直调整到根节点的树,就可以调整成堆(向下调整)。

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

堆内存数据结构,数据结构探索,数据结构,堆,c语言,开发语言,算法

☁️建堆时间复杂度

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

堆内存数据结构,数据结构探索,数据结构,堆,c语言,开发语言,算法

根据上图可以推算出: 建堆的时间复杂度为O(N)。

☁️堆的插入

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

堆内存数据结构,数据结构探索,数据结构,堆,c语言,开发语言,算法

☁️堆的删除

删除堆是删除堆顶的数据,将堆顶的数据根最后一个数据一换,然后删除数组最后一个数据,再进行向下调整算法。

堆内存数据结构,数据结构探索,数据结构,堆,c语言,开发语言,算法

🌤️堆的代码是实现

☁️堆的结构体

typedef int HeapDataType;

typedef struct Heap
{
	HeapDataType* a;
	int size;  //有效元素
	int cpciti; //容量
}HP;
  • HeapDataType 定义了堆中元素的数据类型,这里是整数。
  • struct Heap 定义了一个包含堆数据的结构体,包括一个指向堆数组的指针 ,堆的有效元素个数 ,以及堆的容量 。

☁️堆的初始化

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

首先使用 断言来确保传入的指针 不为空。然后,将堆数组指针设置为 NULL,将堆的有效元素个数和容量都初始化为 0。

☁️堆的销毁

void HeapDestroy(HP* hp)
{
	assert(hp);
	free(hp->a);
	hp->a = NULL;
	hp->size = hp->cpciti = 0;
}

使用 断言确保传入的指针 不为空。然后,使用函数释放堆数组分配的内存,并将指针设置为 NULL。最后,将堆的有效元素个数和容量都设置为 0。

☁️堆的插入

void AdjustUp(HeapDataType* 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* hp, HeapDataType x)
{
	assert(hp);
	//
	if (hp->size == hp->cpciti)
	{
		int newCapacity = hp->cpciti == 0 ? 4 : hp->cpciti * 2;
		HeapDataType* tmp = (HeapDataType*)realloc(hp->a, sizeof(HeapDataType) * newCapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		hp->a = tmp;
		hp->cpciti = newCapacity;
	}
	hp->a[hp->size] = x;
	hp->size++;
	AdjustUp(hp->a, hp->size-1);
}

AdjustUp用于将堆的最后一个节点(即插入的新节点)向上调整,使得以新节点为叶子节点的子树仍然满足堆的性质。具体步骤如下:

  1. 初始化parent为(child - 1) / 2,即新节点的父节点。
  2. 如果child大于0(即child不是根节点),则执行以下操作:
    • 如果child节点的值小于parent节点的值,则交换child和parent节点的值,并更新child为parent,parent为(child - 1) / 2。
    • 否则,跳出循环。
  3. 调整结束。

HeapPush用于向堆中插入一个新的元素。具体步骤如下:

  1. 检查堆的大小是否达到了容量上限,如果是,则进行扩容操作。
  2. 将新元素x放入堆的最后一个位置。
  3. 堆的大小加1。
  4. 调用AdjustUp函数,将新插入的元素向上调整。

☁️堆的删除

void AdjustDown(HeapDataType* 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;
		}
	}
}
void HeapPop(HP* hp)
{
	assert(hp);
	assert(hp->size > 0);

	Swap(&hp->a[0], &hp->a[hp->size - 1]);
	hp->size--;

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

AdjustDown用于将堆的根节点向下调整,使得以根节点为根的子树仍然满足堆的性质。具体步骤如下:

  1. 初始化child为parent的左孩子节点。
  2. 如果child小于n(即child在数组范围内),则执行以下操作:
    • 如果child+1也小于n且右孩子节点的值小于左孩子节点的值,则将child更新为右孩子节点。
    • 如果child节点的值小于parent节点的值,则交换child和parent节点的值,并更新parent为child,child为parent的左孩子节点。
    • 否则,跳出循环。
  3. 调整结束。

HeapPop用于删除堆的根节点。具体步骤如下:

  1. 交换根节点和最后一个节点的值。
  2. 将堆的大小减1。
  3. 调用AdjustDown函数,将根节点向下调整。

☁️取堆顶数据

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

断言来确保传入的指针 是非空的(不为 NULL),以及堆的大小大于0。如果这些条件不满足,程序会终止执行。然后,返回堆的顶部元素,也就是堆数组中的第一个元素。

☁️堆的数据个数

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

size即堆的大小,表示堆中当前包含的元素个数。

☁️堆的判空

int HeapEmpty(HP* hp)
{
	assert(hp);
	return hp->size == 0;
}

断言确保传入的指针不为空,检查堆的大小是否等于0。如果堆的大小为0,函数返回1(表示堆为空),否则返回0(表示堆不为空)。

🌤️堆特性总结

  1. 堆是一棵完全二叉树,即除了最后一层外,其他层都是满的,最后一层从左到右填满。
  2. 堆分为大根堆和小根堆两种,大根堆中每个节点的值都大于其子节点的值,小根堆中每个节点的值都小于其子节点的值。
  3. 堆的根节点是堆中的最小(或最大)元素。
  4. 堆中的任意节点的值都小于(或大于)其子节点的值。
  5. 堆中的元素是按照层序遍历的顺序存储在数组中的,可以用数组来实现堆。
  6. 堆的插入和删除操作分别为向上调整(AdjustUp)和向下调整(AdjustDown),保证插入和删除后仍然满足堆的性质。
  7. 堆的时间复杂度为O(logN),其中N为堆中元素的个数。

🌤️全篇总结

堆作为数据结构中的重要部分,展现了在多种算法和应用中的价值。掌握堆的知识会对你以后解决各种问题和优化性能提供重要帮助。
堆内存数据结构,数据结构探索,数据结构,堆,c语言,开发语言,算法文章来源地址https://www.toymoban.com/news/detail-755127.html

到了这里,关于【数据结构】堆详解!(图解+源码)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】队列篇| 超清晰图解和详解:循环队列模拟、用栈实现队列、用队列实现栈

    博主简介: 努力学习的22级计算机科学与技术本科生一枚🌸 博主主页: @是瑶瑶子啦 每日一言🌼: 每一个不曾起舞的日子,都是对生命的辜负。——尼采 🔗622. 设计循环队列 👧🏻 思路: 🍊数据结构: 使用数组为数据结构,且采用牺牲一个空间的方法来包装判空和判满的

    2024年02月11日
    浏览(38)
  • 【数据结构】数组的顺序存储(1、2、3、n维数组的元素地址计算)|保姆级详解+图解

    作者: 努力学习的大一在校计算机专业学生,热爱学习和创作。目前在学习和分享:算法、数据结构、Java等相关知识。 博主主页: @是瑶瑶子啦 所属专栏: 【数据结构】:该专栏专注于数据结构知识,持续更新,每一篇内容优质,浅显易懂,不失深度! 近期目标: 写好专栏

    2024年02月07日
    浏览(45)
  • 【茶话数据结构】查找最短路径——Dijkstra算法详解(保姆式详细图解,步步紧逼,保你学会)

     💯 博客内容:【茶话数据结构】查找最短路径——Dijkstra算法详解 😀 作  者:陈大大陈 🦉所属专栏:数据结构笔记 🚀 个人简介:一个正在努力学技术的准前端,专注基础和实战分享 ,欢迎私信! 💖 欢迎大家:这里是CSDN,我总结知识和写笔记的地方,喜欢的话请三

    2024年02月08日
    浏览(43)
  • 【数据结构】二叉树篇|超清晰图解和详解:二叉树的序列化和反序列化

    博主简介: 努力学习的22级计算机科学与技术本科生一枚🌸 博主主页: @是瑶瑶子啦 每日一言🌼: 你不能要求一片海洋,没有风暴,那不是海洋,是泥塘——毕淑敏 🍊 序列化 :本质就是 二叉树的遍历 ,就那么几个:前序、中序、后序、层序。而序列化只不过就是 在遍历到

    2024年02月10日
    浏览(47)
  • 【数据结构】C--顺序表1.0版本(本文非常适合小白观看,已尽力详解,以及图解也是尽量列举)

    目录 0.前言 什么是数据结构? 1.逻辑结构: 1.1线性结构: 1.2非线性结构:         (1)集合         (2)树形结构         (3)图形结构或者网状结构 2.存储结构 一.线性表 二.顺序表 顺序表与数组的关系:(非常容易混淆) 1.静态顺序表:使用定长数组存储元素 2.动态顺序表

    2024年02月06日
    浏览(54)
  • 【数据结构】 顺序表详解!(源码+解析)

    🎥 屿小夏 : 个人主页 🔥个人专栏 : 数据结构解析 🌄 莫道桑榆晚,为霞尚满天! ​ 什么是数据结构?我们为什么要学数据结构?数据结构中的顺序表长什么样子?它是怎么运用? ​ 本期我们将对这些一一讲解,彻底明白数据结构的重要性,以及顺序表是一种什么的数据

    2024年02月06日
    浏览(44)
  • 『初阶数据结构 • C语言』⑬ - 堆排序详解【附完整源码】

     = 目录 0.写在前面 1.什么是堆? 2. 堆排序 2.1 建堆 2.1.1 AdjustUp(向上调整算法) 2.1.2 AdjustDown(向下调整算法) 2.2 两种建堆算法的时间复杂度 2.2.1 AdjustUp建堆的时间复杂度 2.2.2 AdjustDown建堆的时间复杂度 2.3 排序 3.堆排序的时间复杂度 完整源码 你是否对堆排序早有耳闻?身

    2024年02月16日
    浏览(36)
  • 『初阶数据结构 • C语言』⑧ - 动态顺序表详解(附完整源码)

    本章内容 写在前面 1.静态与动态是指什么? 2.动态顺序表结构的定义 3.动态顺序表的函数接口实现 4.动态顺序表的问题及思考 5.关于顺序表的OJ题 6.OJ答案及解析 1.移除元素 2.删除有序数组中的重复项 ​3.合并两个有序数组 7.动态顺序表完整源码 1.SeqList.h 2.SeqList.c     上一章

    2024年02月16日
    浏览(43)
  • 【算法与数据结构】深入二叉树实现超详解(全源码优化)

    上节我们学习了二叉树(前中后)序遍历 这节将实现二叉树。 让我们复习一下二叉树,接着就是二叉树的实现了😊,学习起来吧! 满二叉树:一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是说,如果一个二叉树的层数为K,且结点总

    2024年04月11日
    浏览(74)
  • 『初阶数据结构 • C语言』⑦ - 静态顺序表详解(附完整源码)

    本章内容 1.什么是线性表 2.什么是顺序表  3.静态顺序表结构的定义 4.静态顺序表的函数接口实现 5.静态顺序表的问题及思考     线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表、链表、栈、

    2024年02月15日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包