【初阶数据结构】——堆的引入

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

目录

前言

一、二叉树的顺序结构及实现 

1.1二叉树的顺序结构

1.2堆的结构

二、堆的实现

2.1堆向上调整算法(堆的插入)

2.2堆向下调整算法(堆的删除)

2.3建堆的时间复杂度

2.4堆的创建

2.5堆的初始化和空间的销毁

2.6堆的插入

向上调整函数

交换函数

2.7堆的删除

向下调整函数

2.8堆的打印、取值、判空

三、完整代码


前言

上篇文章简单介绍树,讲解了最基本的二叉树,以及二叉树使用数组存储的顺序结构和使用链表存储的链式结构两种存储方式,今天就引入堆来实现二叉树。


一、二叉树的顺序结构及实现 

1.1二叉树的顺序结构

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

【初阶数据结构】——堆的引入,数据结构挨打小记,数据结构,c语言,算法,开发语言

1.2堆的结构

如果有一个关键码的集合K = { k0,k1 ,k1 ,…, },把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中,并满足:Ki<=K2*i+1 且Ki <=K2*i+2 (Ki >=K2*i+1 且Ki >=K2*i+2 ) i = 0,1,2…,则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。 

堆的性质:

堆中某个节点的值总是不大于或不小于其父节点的值。

大堆:任何父亲大于等于孩子

小堆:任何父亲小于等于孩子
堆总是一棵完全二叉树。

【初阶数据结构】——堆的引入,数据结构挨打小记,数据结构,c语言,算法,开发语言


二、堆的实现

2.1堆向上调整算法(堆的插入)

我们直到在数组中插入数据是在末尾插入,那么用堆来表示就是在有效数据下面做孩子或者父亲,依次插入数据和上面的父亲结点作比较,如果父亲大了就将父亲和孩子互换,一直换到度也就是第一个结点就形成小堆,反之则形成大堆。 

【初阶数据结构】——堆的引入,数据结构挨打小记,数据结构,c语言,算法,开发语言

2.2堆向下调整算法(堆的删除)

我么以上面建的小堆为例如果我们删除第一个元素,按照惯例将后面的元素前移,就会形成新的堆但是新的堆不一定是我们的大堆或者小堆上面的情况纯属巧合,通过观察我们可以发现去掉第一个元素形成的左右子树依然是小堆,我们不妨将第一个元素和最后一个元素互换位置,这样最小的元素就在最后,指针前移就可以做到删除,然后第一个位置的两个子树都是小堆再从两个小堆的堆顶选出最小的交换,重复操作又可以是一个小堆了。

【初阶数据结构】——堆的引入,数据结构挨打小记,数据结构,c语言,算法,开发语言

2.3建堆的时间复杂度

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

【初阶数据结构】——堆的引入,数据结构挨打小记,数据结构,c语言,算法,开发语言

2.4堆的创建

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

还是使用动态开辟空间,来实现;

2.5堆的初始化和空间的销毁

void HPInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->size = php->capacity = 0;
}

和顺序表一样,将指针置空和将容量,size置零 。

//销毁空间
void HPDes(HP* php)
{
	assert(php);
	free(php->a);
	php->size = php->capacity = 0;
}

使用free库函数释放动态开辟的空间,最后将容量和size置零。

2.6堆的插入

void HPPush(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->a, sizeof(HPDatatype)*newcapacity);
		if (tmp == NULL)
		{
			perror("realloc failed");
			exit(-1);
		}
		php->a = tmp;
		php->capacity = newcapacity;
	}
	php->a[php->size] = x;
	php->size++;
	HPadjustUp(php->a, php->size-1);
}

和顺序表的形式差不多,进入函数判断空间是否足够,不够的话动态开辟新的空间,开辟不成功的话打印错误码并退出,成功的话插入有效数据,size++,然后使用向上调整函数调整成堆 。

向上调整函数

调整函数就是上面的堆的向上调整算法,运用父亲和孩子的下标关系调整。

void HPadjustUp(HPDatatype* a, int child)
{
	//找到父亲
	int parent = (child - 1) / 2;
	//根为0  当和根交换后child为0
	while (child > 0)
	{
		//当child小时和父亲交换 建成小堆
		//当child大时和父亲交换 建成大堆
		if (a[parent] > a[child])
		{
			swap(&a[parent], &a[child]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

【初阶数据结构】——堆的引入,数据结构挨打小记,数据结构,c语言,算法,开发语言

交换函数

void swap(HPDatatype* x, HPDatatype* y)
{
	HPDatatype tmp = *x;
	*x = *y;
	*y = tmp;
}

取地址防止出函数创建的变量销毁,导致交换失败。

2.7堆的删除

void HPpop(HP* php)
{
	assert(php);
	assert(php->size);
	//先将头和尾交换  左右子树依然是完整的小/大堆,再从两个子堆中找出最大/小值;
	swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;
	HPadjustDown(php->a, php->size, 0);
}

 进入函数先判断,如果size为0是会造成越界,再将头和尾交换,size减减,最后使用堆的向下调整算法调整成小堆。

向下调整函数

void HPadjustDown(HPDatatype* a, int n, int parent)
{
	//假设左孩子最小
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && a[child + 1] < a[child])
		{
			//假设失败 右孩子小
			++child;
		}
		else
		{
			if (a[child] < a[parent])
			{
				swap(&a[child], &a[parent]);
				parent = child;
				child = parent * 2 + 1;
			}
			else
			{
				break;
			}

		}
	}
}

【初阶数据结构】——堆的引入,数据结构挨打小记,数据结构,c语言,算法,开发语言

在这个函数中我们使用了一个假设法我们也不知道子堆的堆顶那个数据最小,但是两者是连续的先假设一个然后进行判断 ;这里一定要注意child的取值范围(child<n),防止越界。

2.8堆的打印、取值、判空

//堆的打印
void HPPrint(HP* php)
{
	for (int i = 0; i < php->size; i++)
	{
		printf("%d ", php->a[i]);
	}
	printf("\n");
}

因为我们创建的是数组,遍历整个数组就可以。

HPDatatype HPtop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	return php->a[0];
}

这里要注意size要大于0,当size为0是代表空。

bool HPempty(HP* php)
{
	assert(php);
	
	return php->size == 0;
}

当size为0时代表空,0==0返回true。


三、完整代码

#define _CRT_SECURE_NO_WARNINGS 67
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int HPDatatype;
typedef struct Heap
{
	HPDatatype* a;
	int size;
	int capacity;
}HP;
//初始化
void HPInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->size = php->capacity = 0;
}
//销毁空间
void HPDes(HP* php)
{
	assert(php);
	free(php->a);
	php->size = php->capacity = 0;
}
void swap(HPDatatype* x, HPDatatype* y)
{
	HPDatatype tmp = *x;
	*x = *y;
	*y = tmp;
}
//
void HPadjustUp(HPDatatype* a, int child)
{
	//找到父亲
	int parent = (child - 1) / 2;
	//根为0  当和根交换后child为0
	while (child > 0)
	{
		//当child小时和父亲交换 建成小堆
		//当child大时和父亲交换 建成大堆
		if (a[parent] > a[child])
		{
			swap(&a[parent], &a[child]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
void HPPush(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->a, sizeof(HPDatatype)*newcapacity);
		if (tmp == NULL)
		{
			perror("realloc failed");
			exit(-1);
		}
		php->a = tmp;
		php->capacity = newcapacity;
	}
	php->a[php->size] = x;
	php->size++;
	HPadjustUp(php->a, php->size-1);
}
void HPPrint(HP* php)
{
	for (int i = 0; i < php->size; i++)
	{
		printf("%d ", php->a[i]);
	}
	printf("\n");
}
void HPadjustDown(HPDatatype* a, int n, int parent)
{
	//假设左孩子最小
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && a[child + 1] < a[child])
		{
			//假设失败 右孩子小
			++child;
		}
		else
		{
			if (a[child] < a[parent])
			{
				swap(&a[child], &a[parent]);
				parent = child;
				child = parent * 2 + 1;
			}
			else
			{
				break;
			}

		}
	}
}

	

void HPpop(HP* php)
{
	assert(php);
	assert(php->size);
	//先将头和尾交换  左右子树依然是完整的小/大堆,再从两个子堆中找出最大/小值;
	swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;
	HPadjustDown(php->a, php->size, 0);
}
HPDatatype HPtop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	return php->a[0];
}
bool HPempty(HP* php)
{
	assert(php);
	
	return php->size == 0;
}
int main()
{
	HP hp;
	HPInit(&hp);
	int a[] = { 65,100,70,32,50,60 };
	for (int i = 0; i < sizeof(a) / sizeof(int); i++)
	{
		HPPush(&hp, a[i]);
	}
	HPPrint(&hp);
	while (!HPempty(&hp))
	{
		printf("%d ", HPtop(&hp));
		HPpop(&hp);
	}
	HPDes(&hp);
	return 0;
}

【初阶数据结构】——堆的引入,数据结构挨打小记,数据结构,c语言,算法,开发语言

最后的执行结果我们可以发现利用堆的删除可以实现排序,这就是我们下篇文章的内容利用堆实现排序,敬请期待!!! 文章来源地址https://www.toymoban.com/news/detail-731985.html

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

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

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

相关文章

  • 数据结构——堆的应用

    堆结构主要有两个应用:1、堆排序 2、topK问题 现实中,排序是非常常见的,比如排序班级同学的各科分数,购物时,商品会按销量,价格,好评数等进行排序。相信大家也不喜欢再购物筛选时,加载半天出不来吧!一个好的排序用的时间会大大减少,改善用户的体验。堆排

    2024年04月10日
    浏览(77)
  • 【数据结构】堆的创建

    堆就是以二叉树的顺序存储方式来存储元素,同时又要满足父亲结点存储数据都要大于儿子结点存储数据或者父亲结点数据都要小于儿子结点数据的一种数据结构。将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。 堆中某个节点的值总是不大于或

    2024年02月07日
    浏览(45)
  • 数据结构:堆的实现

    如果有一个关键码的集合 K = { k1 ,k2 ,k3 ,…,kn },把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中,并且 k(i)  k(i*2+1) 和 k(i)  k(i*2+2), i = 0 , 1 , 2…,则称为小堆 ( 或大堆 ) 。将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小

    2024年02月13日
    浏览(35)
  • 数据结构之堆的结构与实现

    目录 一、堆的概念及结构 1.1堆的概念  1.2堆的性质 1.3堆的结构 二、堆的实现 2.1堆向下调整算法(父亲与孩子做比较)  2.2堆的向上调整算法(孩子与父亲做比较) 2.3堆的创建(向下建堆)  2.4向下建堆的时间复杂度 2.5堆的插入 2.6堆的删除 2.7堆的完整代码实现 三、堆的应

    2024年02月08日
    浏览(40)
  • 数据结构—小堆的实现

    前言:前面我们已经学习了二叉树,今天我们来学习堆,堆也是一个二叉树,堆有大堆有小堆,大堆父节点大于子节点,小堆父节点总小于子节点,我们在学习C语言的时候也有一个堆的概念,那个堆是操作系统中的堆,与我们今天所学的堆全然不同。我们就来实现下小堆。

    2024年02月05日
    浏览(34)
  • 【数据结构】堆:堆的构建,堆的向上调整算法,堆的向下调整算法、堆排序

    目录 一、堆的定义 1、堆的定义: 2、根节点与其左、右孩子间的联系   二、堆的创建 1、堆的向下调整算法  2、堆的向上调整算法  三、堆排序 1、堆的定义: 堆可以被看作是 一棵 完全二叉树 的 数组 对象 。即在 存储结构上是数组,在逻辑结构上是一棵完全二叉树 。在

    2024年01月22日
    浏览(43)
  • 数据结构——二叉树(堆的实现)

    目录   树概念及结构 树的相关概念 树的表示  二叉树的概念及结构   堆 堆的实现   结构体建立 初始化   添加元素  打印堆  删除堆首元素  返回首元素  判断是否为空 空间销毁  刷题找工作的好网站——牛客网 牛客网 - 找工作神器|笔试题库|面试经验|实习招聘内推,

    2024年02月11日
    浏览(45)
  • 【数据结构之堆的实现】

    前言: 前篇学习了 数据结构之树和二叉树的基本概念知识,那么这篇继续学习怎么实现基本的操作。所以先建议看完上篇知识点,才有助于消化知识和理解。 / 知识点汇总 / 概念 :堆(Heap)是计算机科学中一类特殊的数据结构,是最高效的优先级队列。堆通常是一个可以被看

    2024年01月19日
    浏览(43)
  • 数据结构之堆的应用

    在我们学习了堆之后我们知道,无论是大堆还是小堆,堆顶的元素要么最大,要么最小。 对于堆插入的时间复杂度为O(logn)也就是向上调整算法的复杂度,删除一个堆中的元素为O(logn),堆在我们日常生活中还是常用到的。 目录 1.top k问题(优质筛选问题) 2.堆排序 1.向

    2024年02月08日
    浏览(52)
  • 【数据结构】堆的实现及应用

    简单不先于复杂,而是在复杂之后 。 1.1 二叉树的顺序结构 普通的二叉树是不适合用数组来存储的,因为可能会存在大量的空间浪费。 而完全二叉树更适合使用顺序结构存储。 现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储,需要注意的是这里的堆和操作系

    2024年02月21日
    浏览(48)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包