速学数据结构 | 二叉树堆的实现详解篇

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


速学数据结构 | 二叉树堆的实现详解篇,数据结构,c++,开发语言

🎬 鸽芷咕:个人主页

 🔥 个人专栏:《速学数据结构》 《C语言进阶篇》
⛺️生活的理想,就是为了理想的生活!

📋 前言

  🌈hello! 各位宝子们大家好啊,二叉树的概念大家都了解了那么我们今天就看一下
  ⛳️顺序存储究竟是怎么存储的,如何实现增删查改这些功能。
  📚本期文章收录在《数据结构&算法》,大家有兴趣可以看看呐
  ⛺️ 欢迎铁汁们 ✔️ 点赞 👍 收藏 ⭐留言 📝!

一、堆的概念

二叉树顺序存储的最大的一个应用就是堆,也是我们后面学习堆排序以及我们日常生活中的 找大小 TOPK 问题的应用。

  • 那么什么是堆呢?

堆就是由二叉树组成把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中。

  • 其中他一定是一个完全二叉树或者满二叉树
  • 堆中某个结点的值总是不大于或不小于其父结点的值;

速学数据结构 | 二叉树堆的实现详解篇,数据结构,c++,开发语言
其中堆又分大堆和小堆:

  • 将根结点最大的堆叫做最大堆或大根堆。
  • 根结点最小的堆叫做最小堆或小根堆。

二、堆的实现

二叉树的最大应用就是“堆”,所以我们今天来看一下堆是怎么实现的他到底有什么功能呢? 他的结构到底是什么?

  • 其实堆的结构和二叉树是一模一样的,只不过存储方式有差别

我们上面介绍过堆中某个结点的值总是不大于或不小于其父结点的值:

2.1 堆的结构

堆的结构很简单前面介绍的时候其实已经介绍过了:

  • 我们采用数组存储的方法,使用size来记录堆的个数
  • capacity来标识堆的容量

📚 代码演示:

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<string.h>

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

2.2 堆的销毁

俗话说做题先从容易得写诶这次我们就先来从堆的销毁来写这个大家在熟悉不过了:

  • 既然是动态申请的空间直接释放就好了
  • 其他 数据个数 和 容量 置为零

📚 代码演示:

//堆的销毁
void HeapDestory(hp* hp)
{
	assert(hp);

	free(hp->a);
	hp->a = NULL;
	hp->size = hp->capacity = 0;
}

2.3 堆的插入

堆的插入就是本篇文章的重点了,堆的插入方式有很多比如说插入之后向上取整,或者向下取整我们选那个呢?

  • 🔥 因为堆要向下取整的时候,左右子树一定要是堆
  • 所以一般选取的是尾插向上取整

速学数据结构 | 二叉树堆的实现详解篇,数据结构,c++,开发语言

向上取整算法

上述就是向上取整的全部流程就是拿我们插入的数据和他的 父节点 进行比较然后调整交换:

  • 这里有一个特点 parent = (child-1)/ 2 ;
  • 父节点等于子节点 -1 除二

速学数据结构 | 二叉树堆的实现详解篇,数据结构,c++,开发语言

所以我们可以根据这一特性来进行循环调整堆

📚 代码演示:

//向上调整
void adjustup(HeapTypeData* 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;
		}
	}

}

这样我们不就把堆的插入OK了吗?既然建堆都会了那么插入还不简单嘛?

📑注意事项:

  1. 检查容量进行扩容
  2. 注意写入数据
  3. 有效个数要++

📚 代码演示:

//堆的插入
void HeapPush(hp* hp, int x)
{
	assert(hp);

	if (hp->capacity == hp->size)
	{
		int newcapacity = hp->capacity * 2;
		HeapTypeData* tmp = (HeapTypeData*)realloc(hp->a, newcapacity * sizeof(HeapTypeData));
		if (tmp == NULL)
		{
			perror("realloc file");
			exit(-1);
		}

		hp->a = tmp;
		hp->capacity = newcapacity;
	}

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

	adjustup(hp->a, hp->size - 1);
}

2.4 堆的删除

堆的删除一般我们都是删除其堆顶的数据:

  • 所以一般是采用向下取整,把堆顶和堆尾进行互换然后再删除堆尾。
  • 把堆顶数据向下调整

速学数据结构 | 二叉树堆的实现详解篇,数据结构,c++,开发语言
这里要控制好循环结束的条件当child < 堆的个数的时候就停止:

  • 而且左孩子节点一定是 child = parent* 2+1;
    速学数据结构 | 二叉树堆的实现详解篇,数据结构,c++,开发语言

📚 代码演示:

//向下调整
void adjustdown(HeapTypeData* 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);

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

	adjustdown(hp->a, hp->size, 0);

}

2.5 取堆顶的数据

这个很简单啦!直接秒杀堆顶数据,我们是从数组开头顺序存放的所以 hp->a[ 0 ]

  • 数组访问就好了

📚 代码演示:

//堆顶元素
void HeapTop(hp* hp)
{
	assert(hp);
	return hp->a[0];
}

2.6 堆的数据个数

数据个数 hp->size 就是用来记录有效数据个数的我们直接返回就可以了:

📚 代码演示:

//堆的数据个数
void HeapSize(hp* hp)
{
	assert(hp);

	return hp->size;
}

2.7 堆的判空

当堆的有效数据为零的时候堆就是空的

//堆的判空 
void HeapEmpty(hp* hp)
{
	assert(hp);

	return hp->size == 0;
}

📝全篇总结

☁️ 好了以上就是全部的建堆代码啦,大家快去实践起来吧!
看到这里了还不给博主扣个:
⛳️ 点赞☀️收藏 ⭐️ 关注

💛 💙 💜 ❤️ 💚💓 💗 💕 💞 💘 💖
拜托拜托这个真的很重要!
你们的点赞就是博主更新最大的动力!
有问题可以评论或者私信呢秒回哦。
速学数据结构 | 二叉树堆的实现详解篇,数据结构,c++,开发语言文章来源地址https://www.toymoban.com/news/detail-789032.html

到了这里,关于速学数据结构 | 二叉树堆的实现详解篇的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 速学数据结构 | 树 森林 二叉树 的概念详讲篇

    🎬 鸽芷咕 :个人主页  🔥 个人专栏 :《速学数据结构》 《C语言进阶篇》 ⛺️生活的理想,就是为了理想的生活!    🌈 hello! 各位宝子们大家好啊,关于线性表我们已经在前面更新完了!    ⛳️ 今天就来看一下复杂一些的数据结构 “树” 他的应用主要在哪些方面

    2024年02月04日
    浏览(38)
  • 二叉树的顺序结构以及堆的实现——【数据结构】

    W...Y的主页 😊 代码仓库分享  💕 上篇文章,我们认识了什么是树以及二叉树的基本内容、表示方法……接下来我们继续来深入二叉树,感受其中的魅力。 目录  二叉树的顺序结构 堆的概念及结构 堆的实现   堆的创建  堆的初始化与释放空间  堆的插入 堆的删除  堆实

    2024年02月07日
    浏览(42)
  • 【数据结构和算法】---二叉树(2)--堆的实现和应用

    如果有一个数字集合,并把它的所有元素 按完全二叉树的顺序存储方式存储在一个一维数组中 ,且在逻辑结构(即二叉树)中,如果 每个父亲节点都大于它的孩子节点那么此堆可以称为大堆 ;那么如果 每个父亲节点都小于它的孩子节点那么此堆可以称为小堆 。 堆的 性质

    2024年02月03日
    浏览(45)
  • 数据结构——lesson7二叉树 堆的介绍与实现

    啦啦啦~这里是土土数据结构学习笔记🥳🥳 💥个人主页:大耳朵土土垚的博客 💥 所属专栏:数据结构学习笔记 💥对于数据结构顺序表链表有疑问的都可以在上面数据结构的专栏进行学习哦~ 欢迎大家🥳🥳点赞✨收藏💖评论哦~🌹🌹🌹 有问题可以写在评论区或者私信我

    2024年03月11日
    浏览(38)
  • 【数据结构】树二叉树的概念以及堆的详解

    ✨链接1:【数据结构】顺序表 ✨链接2:【数据结构】单链表 ✨链接3:【数据结构】双向带头循环链表 ✨链接4:【数据结构】栈和队列 百度百科的解释 :树是一种 非线性 的数据结构,它是由n(n≥0)个有限节点组成一个具有层次关系的集合。 把它叫做树是因为它看起来像

    2024年02月16日
    浏览(37)
  • 【数据结构】堆的应用+TOP-K问题+二叉树遍历

    欢迎来到我的: 世界 希望作者的文章对你有所帮助,有不足的地方还请指正,大家一起学习交流 ! 该篇文章写到主要是:堆排序、 TOP-K问题、二叉树链式结构的实现、二叉树的遍历等等;如果有朋友还不太了解堆以及二叉树可以翻看我的上一篇博客:堆和二叉树的概念; 最

    2024年02月07日
    浏览(51)
  • 【数据结构】由完全二叉树引申出的堆的实现

    关于“堆”,百度百科上是这么说的: ——————————引自百度百科 由上面可知,我们可以将堆理解成一个数组,也可以理解成一个完全二叉树。 其实由于完全二叉树的特殊性,其本身就可以使用一个数组来存储。 在之前的二叉树的实现中,我们已经知道完全二叉树

    2024年02月08日
    浏览(43)
  • 【数据结构—二叉树的基础知识介绍和堆的实现(顺序表)】

    提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言 1.树概念及结构 1.1树的概念 1.2 树的相关概念  1.3 树的表示 1.4 树在实际中的运用(表示文件系统的目录树结构) 2.二叉树概念及结构 2.1概念 2.2 特殊的二叉树: 2.3 二叉树的存储结构

    2024年02月03日
    浏览(41)
  • 数据结构入门(C语言版)二叉树的顺序结构及堆的概念及结构实现应用

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

    2023年04月19日
    浏览(51)
  • 【数据结构初阶】七、非线性表里的二叉树(堆的实现 -- C语言顺序结构)

    ========================================================================= 相关代码gitee自取 : C语言学习日记: 加油努力 (gitee.com)  ========================================================================= 接上期 : 【数据结构初阶】六、线性表中的队列(链式结构实现队列)-CSDN博客  ===========================

    2024年02月08日
    浏览(44)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包