【数据结构】结构实现:顺序存储模式实现堆的相关操作

这篇具有很好参考价值的文章主要介绍了【数据结构】结构实现:顺序存储模式实现堆的相关操作。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

🚩纸上得来终觉浅, 绝知此事要躬行。
🌟主页:June-Frost
🚀专栏:数据结构

【数据结构】结构实现:顺序存储模式实现堆的相关操作,数据结构,数据结构,堆,顺序存储,二叉树

🔥该文章着重讲解了使用顺序结构实现堆的插入和删除等操作。

🌍二叉树的顺序结构

 二叉树的顺序存储是指将二叉树中的所有节点按照一定的顺序(一层一层)存储到一个数组中。
【数据结构】结构实现:顺序存储模式实现堆的相关操作,数据结构,数据结构,堆,顺序存储,二叉树
 我们可以通过数组下标来表示节点之间的父子关系。

找左孩子节点:leftchild = parent * 2 + 1
找右孩子节点:rightchild = parent * 2 + 2

例如,找B的左孩子 : B的下标 * 2 + 1,得到3 ,即为D。

找父亲节点:parent = ( child -1 )/ 2

例如,找G的父母:(G的下标-1)/ 2 得到 2 ,即为C 。

 需要注意的是,二叉树的顺序存储适用于满二叉树或完全二叉树的情况,对于其他类型的二叉树,顺序存储可能会造成空间浪费访问效率低下的问题。

例如:
【数据结构】结构实现:顺序存储模式实现堆的相关操作,数据结构,数据结构,堆,顺序存储,二叉树
 这类二叉树不适合顺序存储,适合链式存储。

🔭 堆

 数据结构中还衍生出了一个结构 —— 堆 , 堆是非线性结构,也是一种完全二叉树。堆的两个常见类型是大堆和小堆。在大堆中,父节点的值总是大于或等于其子节点的值;而在小堆中,父节点的值总是小于或等于其子节点的值。堆通常用数组来实现。
 所以,对于任意一个数组是可以看作一颗完全二叉树,但不一定是堆。


🌏 代码实现

 这里将实现堆的插入和删除,以小堆为例。
 堆的结构特点是:存储结构——数组,逻辑结构——完全二叉树。所以可以定义结构体为:

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

✉️ 堆的插入

 插入的需求为:无论如何插入,都必须保持为堆。因为存储结构是数组,所以选择效率更快的尾插,然后再进行调整(插入的数据会影响它的祖先)。
 调整部分有这样的3种场景:

  1. 不会影响祖先

【数据结构】结构实现:顺序存储模式实现堆的相关操作,数据结构,数据结构,堆,顺序存储,二叉树
2.影响部分,但不影响到根。

【数据结构】结构实现:顺序存储模式实现堆的相关操作,数据结构,数据结构,堆,顺序存储,二叉树
3.影响到全部祖先

【数据结构】结构实现:顺序存储模式实现堆的相关操作,数据结构,数据结构,堆,顺序存储,二叉树
注:这种调整是向上调整。时间复杂度为 O(logN)

💫调整的条件:
【数据结构】结构实现:顺序存储模式实现堆的相关操作,数据结构,数据结构,堆,顺序存储,二叉树

📙实现代码:

//交换数据
void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
//向上调整
void AdjustUp(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if(a[parent] > a[child])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (parent - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
//插入数据
void HeapPush(HP* php, HPDataType x)
{
	assert(php);
	if (php->capacity == php->size)
	{
		int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(php->a,sizeof(HPDataType) * newCapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		php->a = tmp;
		php->capacity = newCapacity;
	}
	php->a[php->size] = x;
	php->size++;
    //向上调整
	AdjustUp(php->a, php->size - 1);
}

✉️ 堆的删除

 在堆中,删除栈顶元素才是有意义的,这样经过调整后,根就是次小或次大的值。由于堆的存储结构是数组,尾插尾删的效率很高,所以可以考虑将根和最后一个数组元素交换,然后不断调整。

【数据结构】结构实现:顺序存储模式实现堆的相关操作,数据结构,数据结构,堆,顺序存储,二叉树
这样的操作之后,可以发现一个特性:左右子树依旧是小堆。


【数据结构】结构实现:顺序存储模式实现堆的相关操作,数据结构,数据结构,堆,顺序存储,二叉树
注:这种调整方式为向下调整,时间复杂度为O(logN)。

💫调整条件:
 当子节点的下标超出数组范围时,说明已经没有子节点了,已经换到了叶子。(针对实现的代码而言,是已经没有了左孩子,因为堆是完全二叉树,自然也就没有右孩子,说明换到了叶子)

📙实现代码:

//向下调整
void AdjustDown(HPDataType* a, int n, int parent)
{
	int child = parent * 2 + 1;//假设左孩子最小
	while (child < n)
	{
		if (child + 1 < n && a[child + 1] < a[child])//注意判断child+1是否越界
		{
			//修正
			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--;
	AdjustDown(php->a, php->size, 0);
}

✉️ 其他部分

一些简单的接口:

//初始化
void HeapInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->size = 0;
	php->capacity = 0;
}
//销毁
void HeapDestroy(HP* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->capacity = php->size = 0;

}
//打印元素
void HeapPrint(HP* php)
{
	assert(php);
	int i = 0;
	for (i = 0; i < php->size; i++)
	{
		printf("%d ", php->a[i]);
	}
	printf("\n");
}
//取堆顶元素
HPDataType HeapTop(HP* php)
{
	assert(php);
	assert(php->size > 0);

	return php->a[0];
}
//判空
bool HeapEmpty(HP* php)
{
	assert(php);

	return php->size == 0;
}

❤️ 结语

 文章到这里就结束了,如果对你有帮助,你的点赞将会是我的最大动力,如果大家有什么问题或者不同的见解,欢迎大家的留言~文章来源地址https://www.toymoban.com/news/detail-719533.html

到了这里,关于【数据结构】结构实现:顺序存储模式实现堆的相关操作的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 【数据结构】线性表的顺序存储结构及实现——C语言版

    线性表的顺序存储结构称为 顺序表 ,其基本思想是 用一段地址连续的存储单元一次存储线性表的数据元素。 设顺序表的每个元素占用 c 个存储单元,则第 i 个元素的存储地址为: 所以, 只要确定了存储顺序表的起始地址(即基地址),计算任意一个元素的存储地址的时间

    2024年03月15日
    浏览(52)
  • 【数据结构】详谈队列的顺序存储及C语言实现

    大家好,很高兴又和大家见面啦!!! 在上一篇内容中,我们在介绍完队列的基本概念、重要术语以及基本操作后,又回顾了一下数据结构的三要素——数据的逻辑结构、数据的存储结构以及数据的运算。 队列这种数据结构我们已经介绍了它的逻辑结构以及数据运算的定义

    2024年01月21日
    浏览(73)
  • 数据结构<树和二叉树>顺序表存储二叉树实现堆排

    ✨Blog:🥰不会敲代码的小张:)🥰 🉑推荐专栏: C语言 🤪、 Cpp 😶‍🌫️、 数据结构初阶 💀 💽座右铭:“ 記住,每一天都是一個新的開始😁😁😁 ” 💀本章内容: 《树和二叉树》的介绍✨ 树是一种非线性的数据结构,它是由n(n=0)个有限结点组成一个具有层次关系

    2024年02月12日
    浏览(43)
  • 数据结构进阶篇 之 【二叉树顺序存储(堆)】的整体实现讲解(赋完整实现代码)

    做人要谦虚,多听听别人的意见,然后记录下来,看看谁对你有意见 3.1 向下调整算法 AdJustDown 3.2 向上调整算法 AdJustUP 3.3 堆的创建 3.3.1 向上建堆 3.3.2 向下建堆 3.3.3 堆的初始化与销毁 3.3.4 堆的插入(压栈) 3.3.5 取堆顶的数据 3.3.6 堆的删除 3.3.7 堆的数据个数 3.3.8 堆的判空

    2024年04月17日
    浏览(72)
  • 头歌(C语言)-数据结构与算法-栈的实现-第1关:实现一个顺序存储的栈

    任务描述 相关知识 栈的基本概念 栈结构的定义(C) 顺序栈的操作 编程要求 测试说明 任务描述 本关任务是实现 step1/SeqStack.cpp 中的 SS_IsFull 、 SS_IsEmpty 、 SS_Length 、 SS_Push 和 SS_Pop 五个操作函数,以实现判断栈是否为满、是否为空、求栈元素个数、进栈和出栈等功能。 相关

    2024年02月07日
    浏览(60)
  • 头歌(C语言)-数据结构与算法-队列-第1关:实现一个顺序存储的队列

    任务描述 相关知识 顺序存储的队列 顺序队列的主要操作 编程要求 测试说明 任务描述 本关任务:实现 step1/SeqQueue.cpp 中的 SQ_IsEmpty 、 SQ_IsFull 、 SQ_Length 、 SQ_In 和 SQ_Out 五个操作函数,以实现判断队列是否为空、是否为满、求队列长度、队列元素入队和出队等功能。 相关知

    2024年02月06日
    浏览(143)
  • 【数据结构】(顺序表)C语言实现线性表顺序存储的创建、插入、删除、查找、输出等基本操作(附完整代码)

    要求:利用书本上的线性表的顺序存储结构定义 #define MAXSIZE 100 //顺序表可能达到的最大长度 typedef struct{ ElemType *elem; // 存储空间基址 int length; // 当前长度 int listsize; // 当前分配的存储容量(以sizeof(ElemType)为单位) } SqList; 1)编写完成下列功能的函数: (1)初始化一个线性表

    2024年04月28日
    浏览(47)
  • 数据结构:线性表顺序存储结构———顺序表

    目录 顺序表的定义 初始化线性表 销毁线性表 求线性表的长度 判断是否为空表 插入数据元素 逻辑序号与物理序号的区别 删除数据元素 输出线性表  按序号求线性表中的元素 按元素值查找 整体上创建顺序表 顺序表实验 线性表的顺序存储是把线性表中的所有元素按照其逻辑

    2024年02月03日
    浏览(45)
  • 数据结构中: 一元多项式的运算(相加,相减,相乘)------用C语言 / C++来实现。 数据结构线性表的操作和应用(顺序存储)

    线性表的操作和应用(顺序存储)。用顺序存储实现一元多项式,并进行加、减、乘运算。 (1)一元多项式结构体创建  (2)初始化 (3)一元多项式赋值             (4)打印一元多项式 (5)加法运算                        (6)减法运算 (7)乘法运算    全部代

    2024年02月01日
    浏览(59)
  • 数据结构与算法——顺序表(顺序存储结构)及初始化详解

    顺序表 ,全名 顺序存储结构 ,是线性表的一种。通过《什么是线性表》一节的学习我们知道,线性表用于存储逻辑关系为“一对一”的数据,顺序表自然也不例外。 不仅如此,顺序表对数据的物理存储结构也有要求。 顺序表存储数据时,会提前申请一整块足够大小的物理

    2024年02月16日
    浏览(39)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包