【数据结构】堆的创建

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

一、堆的概念及结构

1、什么是堆

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

2、堆的性质

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

3、堆的结构及分类

【数据结构】堆的创建,数据结构,C语言,数据结构,算法,c语言
小堆:所有的双亲结点都小于孩子节点,根节点最小
【数据结构】堆的创建,数据结构,C语言,数据结构,算法,c语言
大堆:所有的双亲结点都大于孩子节点,根节点最大

二、堆的创建

后面代码用到的堆结构体:

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

重要关系:
【数据结构】堆的创建,数据结构,C语言,数据结构,算法,c语言

1、堆向下调整算法

例如有一个数组:

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

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

【数据结构】堆的创建,数据结构,C语言,数据结构,算法,c语言
【数据结构】堆的创建,数据结构,C语言,数据结构,算法,c语言

以下代码是用向下调整法调整为小堆:

//向下调整
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++;
		}
		//孩子节点更小则交换
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

2、堆向上调整算法

例如对如下小堆:
【数据结构】堆的创建,数据结构,C语言,数据结构,算法,c语言
该小堆插入数字1后就不是小堆了,需要用从这个元素开始的向上调整算法对它进行调整。

向上调整有一个前提:前面的元素是堆

【数据结构】堆的创建,数据结构,C语言,数据结构,算法,c语言
以下代码是用向上调整法调整为小堆:

//向上调整
void AdjustUp(HPDataType* a, int child)
{
	//找出双亲的下标
	int parent = (child - 1) / 2;

	while (child>0)
	{
		//孩子结点比双亲小则交换
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

3、堆的创建(向上调整算法)

向上调整算法和向下调整算法想要使用都有前提,对于一个数组,想要让它在逻辑结构上可以看作一个堆,那就可以先让它满足这两种算法其中一种的条件,然后进行调整即可。

对于单个结点来说既可以看作大堆也可以看作小堆,所有便可以通过向上调整算法依次对数组元素进行调整,那进行调整的元素前就一定是堆,满足条件,以下为该方法的代码:

// 堆的构建
void HeapCreate(Heap* hp, HPDataType* a, int n)
{
	assert(hp);
	assert(a);

    //开辟存放堆元素的内存空间
	hp->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
	if (hp->a == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}

	hp->size = n;
	hp->capacity = n;

    //将数组元素复制到堆中存放元素的内存空间内
	memcpy(hp->a, a, sizeof(HPDataType) * n);

    //从下标1开始进行向上调整
	for (int i = 1; i < n; i++)
	{
		AdjustUp(hp->a, i);
	}
}

【数据结构】堆的创建,数据结构,C语言,数据结构,算法,c语言文章来源地址https://www.toymoban.com/news/detail-726905.html

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

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

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

相关文章

  • 『初阶数据结构 • C语言』⑫ - 堆的概念&&实现(图文详解+完整源码)

    目录 0.写在前面 1.什么是堆? 2.堆的实现 2.1 堆的结构定义 2.2 函数声明 2.3 函数实现 2.3.1 AdjustUp(向上调整算法) 2.3.2 AdjustDown(向下调整算法) 2.3.3 HeapCreate(如何建堆) 2.3.4 建堆的时间复杂度 3. 完整源码 Heap.h文件 Heap.c文件  Test.c文件  上一章中介绍了树和二叉树的概念

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

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

    2024年02月08日
    浏览(44)
  • 【数据结构】长篇详解堆,堆的向上/向下调整算法,堆排序及TopK问题

    堆就是将一组数据所有元素按完全二叉树的顺序存储方式存储在一个 一维数组 中,并满足树中 每一个父亲节点都要大于其子节点 称为 大堆 (树中 每一个父亲节点都要大于其子节点 称为 小堆 )。 性质 ①对于大堆(大根堆)来说,堆的顶部也就是数组首元素一定是最大的元素 ②

    2024年02月07日
    浏览(40)
  • 【数据结构】向上调整建堆和向下调整建堆的天壤之别以及堆排序算法

       💯 博客内容:【数据结构】向上调整建堆和向下调整建堆的天壤之别以及堆排序算法 😀 作  者:陈大大陈 🚀 个人简介:一个正在努力学技术的准前端,专注基础和实战分享 ,欢迎私信! 💖 欢迎大家:这里是CSDN,我总结知识和写笔记的地方,喜欢的话请三连,有

    2024年02月06日
    浏览(46)
  • 数据结构——堆的应用

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

    2024年04月10日
    浏览(77)
  • 数据结构---堆的实现

    前言 一、什么是堆? 二、 堆的实现 1. 堆的结构  2. 接口实现 总结 堆(Heap)是计算机科学中一类特殊的数据结构,是最高效的优先级队列。堆通常是一个可以被看做一棵完全二叉树的数组对象。 现实中我们通常把 堆(一种二叉树) 使用 顺序结构的数组 来存储, 大根堆 :根节

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

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

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

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

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

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

    2024年02月05日
    浏览(33)
  • 数据结构之堆的应用

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

    2024年02月08日
    浏览(50)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包