前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >速学数据结构 | 二叉树堆的实现详解篇

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

作者头像
鸽芷咕
发布2023-12-25 15:15:08
1000
发布2023-12-25 15:15:08
举报
文章被收录于专栏:C++干货基地C++干货基地
在这里插入图片描述
在这里插入图片描述

🎬 鸽芷咕个人主页 🔥 个人专栏:《速学数据结构》 《C语言进阶篇》

⛺️生活的理想,就是为了理想的生活!


📋 前言

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

文章目录
  • 📋 前言
  • 一、堆的概念
  • 二、堆的实现
    • 2.1 堆的结构
    • 2.2 堆的销毁
    • 2.3 堆的插入
      • 向上取整算法
    • 2.4 堆的删除
    • 2.5 取堆顶的数据
    • 2.6 堆的数据个数
    • 2.7 堆的判空
  • 📝全篇总结

一、堆的概念

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

  • 那么什么是堆呢?

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

  • 其中他一定是一个完全二叉树或者满二叉树
  • 堆中某个结点的值总是不大于或不小于其父结点的值;
在这里插入图片描述
在这里插入图片描述

其中堆又分大堆和小堆:

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

二、堆的实现

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

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

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

2.1 堆的结构

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

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

📚 代码演示:

代码语言:javascript
复制
#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 堆的销毁

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

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

📚 代码演示:

代码语言:javascript
复制
//堆的销毁
void HeapDestory(hp* hp)
{
	assert(hp);

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

2.3 堆的插入

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

  • 🔥 因为堆要向下取整的时候,左右子树一定要是堆
  • 所以一般选取的是尾插向上取整
在这里插入图片描述
在这里插入图片描述
向上取整算法

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

  • 这里有一个特点 parent = (child-1)/ 2 ;
  • 父节点等于子节点 -1 除二
在这里插入图片描述
在这里插入图片描述

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

📚 代码演示:

代码语言:javascript
复制
//向上调整
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. 有效个数要++

📚 代码演示:

代码语言:javascript
复制
//堆的插入
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 堆的删除

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

  • 所以一般是采用向下取整,把堆顶和堆尾进行互换然后再删除堆尾。
  • 把堆顶数据向下调整
在这里插入图片描述
在这里插入图片描述

这里要控制好循环结束的条件当child < 堆的个数的时候就停止:

  • 而且左孩子节点一定是 child = parent* 2+1;
在这里插入图片描述
在这里插入图片描述

📚 代码演示:

代码语言:javascript
复制
//向下调整
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;
		}
	}
}

然后我们进行交换堆顶 和堆数据在进行更改有效个数

  • 调整一下堆的删除就完了

📚 代码演示:

代码语言:javascript
复制
//堆的删除
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 ]

  • 数组访问就好了

📚 代码演示:

代码语言:javascript
复制
//堆顶元素
void HeapTop(hp* hp)
{
	assert(hp);
	return hp->a[0];
}

2.6 堆的数据个数

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

📚 代码演示:

代码语言:javascript
复制
//堆的数据个数
void HeapSize(hp* hp)
{
	assert(hp);

	return hp->size;
}

2.7 堆的判空

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

代码语言:javascript
复制
//堆的判空 
void HeapEmpty(hp* hp)
{
	assert(hp);

	return hp->size == 0;
}

📝全篇总结

☁️ 好了以上就是全部的建堆代码啦,大家快去实践起来吧! 看到这里了还不给博主扣个: ⛳️ 点赞☀️收藏 ⭐️ 关注 💛 💙 💜 ❤️ 💚💓 💗 💕 💞 💘 💖 拜托拜托这个真的很重要! 你们的点赞就是博主更新最大的动力! 有问题可以评论或者私信呢秒回哦。

在这里插入图片描述
在这里插入图片描述
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2023-12-25,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 📋 前言
    • 文章目录
    • 一、堆的概念
    • 二、堆的实现
      • 2.1 堆的结构
        • 2.2 堆的销毁
          • 2.3 堆的插入
            • 向上取整算法
          • 2.4 堆的删除
            • 2.5 取堆顶的数据
              • 2.6 堆的数据个数
                • 2.7 堆的判空
                • 📝全篇总结
                相关产品与服务
                对象存储
                对象存储(Cloud Object Storage,COS)是由腾讯云推出的无目录层次结构、无数据格式限制,可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限,无需分区管理,适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。
                领券
                问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档