堆的介绍,实现(c语言实现)

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

目录

堆的概念

堆的性质:

堆的分类 

父子结点的下标关系

堆的向下调整算法

​编辑小堆 

大堆

 建堆

堆的向上调整算法

小堆

 大堆

堆的基本操作

定义堆

初始化堆

 销毁堆

打印堆

堆的插入

堆的删除

大堆(Max Heap)的向下调整算法思路:

小堆(Min Heap)的向下调整算法思路:

关键点解释:

获取堆的数据个数

堆的判空


堆的概念

如果有一个关键码的集合K = { k1,k2 ,k3 ,…, },把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中,并满足:堆的介绍,实现(c语言实现),数据结构初阶,数据结构,算法,排序算法i = 0,1, 2…,则称为小堆(或大堆)。

在数据结构中,堆(Heap)是一种特殊的树形数据结构,通常被实现为完全二叉树或近似完全二叉树。堆的一个重要特性是它满足堆属性,即每个节点的值都大于或等于(在最大堆中)或小于或等于(在最小堆中)其子节点的值。

堆在计算机科学中有广泛的应用,尤其是在实现优先队列和堆排序算法中。优先队列是一种数据结构,其中元素的优先级决定了它们的出队顺序。堆可以作为一种高效的优先队列实现方式,因为堆顶元素总是优先级最高(最大或最小)的元素。堆排序算法则利用堆的性质,通过构建最大堆或最小堆,并反复取出堆顶元素来实现排序。

将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。

堆的性质:

  1. 堆中某个节点的值总是不大于或不小于其父节点的值;
  2. 堆总是一棵完全二叉树。

堆的分类 

堆主要分为两种类型:最大堆(Max Heap)和最小堆(Min Heap)。在最大堆中,父节点的值总是大于或等于其子节点的值,因此堆顶元素是整个堆中的最大值。相反,在最小堆中,父节点的值总是小于或等于其子节点的值,堆顶元素是整个堆中的最小值。 

堆通常使用数组来实现,数组中的每个元素对应堆中的一个节点。由于堆是完全二叉树,所以可以使用数组的下标关系来模拟树中父节点和子节点之间的关系。这种实现方式使得堆在插入、删除和查找最大(或最小)元素等操作中具有高效的性能。

堆的介绍,实现(c语言实现),数据结构初阶,数据结构,算法,排序算法 堆的介绍,实现(c语言实现),数据结构初阶,数据结构,算法,排序算法

父子结点的下标关系

在堆的数据结构中,我们通常将数组中的每个元素视为一个结点,这些结点按照完全二叉树的顺序存储在数组中。每个结点都有一个唯一的下标,通过下标关系,我们可以确定任意结点的父结点和子结点的位置。

对于给定下标 i 的结点,其父结点、左子结点和右子结点的下标可以通过以下关系式计算:

  • 下标i元素的父结点下标:(i - 1) / 2(使用整数除法)
  • 下标i元素的左子结点下标:2 * i + 1
  • 下标i元素的右子结点下标:2 * i + 2

这些关系式基于完全二叉树的性质。在完全二叉树中,除了最后一层,其他层的结点是满的,且最后一层的结点都靠左对齐。因此,对于任意结点,其左子结点的下标是其下标的两倍加一,右子结点的下标是其下标的两倍加二,而父结点的下标则是通过将其下标减一后除以二(整数除法)得到。

通过这些下标关系,我们可以方便地在数组中进行堆的操作,如插入、删除、堆化等。例如,在插入新元素时,我们可以将其放在数组的末尾,并通过与其父结点比较和交换(如果需要)来维护堆的性质。同样地,在删除堆顶元素时,我们可以将数组的最后一个元素移动到堆顶,并通过与其子结点比较和交换来重新调整堆。

需要注意的是,当使用这些下标关系时,我们需要确保下标不会超出数组的范围。例如,根结点的下标为 0,它没有父结点。对于任意结点,我们需要检查其左子结点和右子结点的下标是否超出了数组的长度,以避免访问不存在的元素。

通过使用结点和下标关系,我们可以高效地实现堆的数据结构,并利用其特性进行各种操作,如快速找到最大(或最小)元素、插入新元素、删除元素等。

堆的向下调整算法

现在我们给出一个数组,逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整 成一个小堆。

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

​​​​​​​堆的介绍,实现(c语言实现),数据结构初阶,数据结构,算法,排序算法

但是,使用向下调整算法需要满足一个前提:

  1.  若想将其调整为小堆,那么根结点的左右子树必须都为小堆。
  2.  若想将其调整为大堆,那么根结点的左右子树必须都为大堆。

小堆 

向下调整算法的基本思想(以建小堆为例):

  1. 从根结点处开始,选出左右孩子中值较小的孩子。
  2. 让小的孩子与其父亲进行比较。

       (1) 若小的孩子比父亲还小,则该孩子与其父亲的位置进行交换。并将原来小的孩子的位置                   当成父亲继续向下进行调整,直到调整到叶子结点为止。
        (2)若小的孩子比父亲大,则不需处理了,调整完成,整个树已经是小堆了。

//交换函数
void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}

//堆的向下调整(小堆)
void AdjustDown(HPDataType* a, int n, int parent)
{
	//child记录左右孩子中值较小的孩子的下标
	int child = 2 * parent + 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 = 2 * parent + 1;
		}
		else//已成堆
		{
			break;
		}
	}
}

大堆

向下调整算法的基本思想(以建大堆为例)如下:

  1. 从根结点处开始,选出左右孩子中值较大的孩子。

  2. 让较大的孩子与其父亲进行比较。

    若较大的孩子比父亲还大,则该孩子与其父亲的位置进行交换。并将原来较大的孩子的位置当成父亲继续向下进行调整,直到调整到叶子结点为止。

    若较大的孩子比父亲小或者没有孩子(即已经是叶子结点),则不需处理了,调整完成,整个树已经是大堆了。

//交换函数
void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}

//堆的向下调整(大堆)  
void AdjustDown(HPDataType* a, int n, int parent)  
{  
    int child = parent * 2 + 1; // 计算左子节点的索引  
  
    // 当 child 索引在数组范围内时执行循环  
    while (child < n)  
    {  
        // 如果右子节点存在且大于左子节点  
        if (child + 1 < n && a[child+1] > a[child])  
        {  
            ++child; // 更新 child 为右子节点的索引  
        }  
  
        // 如果 child 节点(现在是左右子节点中较大的一个)大于 parent 节点  
        if (a[child] > a[parent])  
        {  
            Swap(&a[child], &a[parent]); // 交换 parent 和 child 的值  
            parent = child; // 更新 parent 为刚刚交换过的 child 的索引  
            child = parent * 2 + 1; // 重新计算左子节点的索引  
        }  
        else  
        {  
            break; // child 节点不大于 parent 节点,无需继续调整,退出循环  
        }  
    }  
}

 使用堆的向下调整算法,最坏的情况下(即一直需要交换结点),需要循环的次数为:h - 1次(h为树的高度)。而堆的介绍,实现(c语言实现),数据结构初阶,数据结构,算法,排序算法(N为树的总结点数)。所以堆的向下调整算法的时间复杂度为:O(logN) 。 

 建堆

 上面说到,使用堆的向下调整算法需要满足其根结点的左右子树均为大堆或是小堆才行,那么如何才能将一个任意树调整为堆呢?

答案很简单,我们只需要从倒数第一个非叶子结点开始,从后往前,按下标,依次作为根去向下调整即可。

堆的介绍,实现(c语言实现),数据结构初阶,数据结构,算法,排序算法

代码

	//建堆
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(php->a, php->size, i);
	}

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

堆的介绍,实现(c语言实现),数据结构初阶,数据结构,算法,排序算法

堆的介绍,实现(c语言实现),数据结构初阶,数据结构,算法,排序算法 所以T(n)=O(N)

总结一下:
 堆的向下调整算法的时间复杂度:T(n)=O(logN)。
 建堆的时间复杂度:T(n)=O(N)。

堆的向上调整算法

当我们在一个堆的末尾插入一个数据后,需要对堆进行调整,使其仍然是一个堆,这时需要用到堆的向上调整算法。

堆的介绍,实现(c语言实现),数据结构初阶,数据结构,算法,排序算法

小堆

向上调整算法的基本思想(以建小堆为例):

  1. 将目标结点与其父结点比较。
  2. 若目标结点的值比其父结点的值小,则交换目标结点与其父结点的位置,并将原目标结点的父 结点当作新的目标结点继续进行向上调整。
  3. 若目标结点的值比其父结点的值大,则停止向上调整,此时该树已经是小堆了。

堆的介绍,实现(c语言实现),数据结构初阶,数据结构,算法,排序算法

//交换函数
void Swap(HPDataType* x, HPDataType* y)
{
	HPDataType tmp = *x;
	*x = *y;
	*y = tmp;
}

//堆的向上调整(小堆)
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;
		}
	}
}

 大堆

向上调整算法的基本思想(以建大堆为例)如下:

  1. 将目标结点与其父结点比较。
  2. 若目标结点的值大于其父结点的值,则交换目标结点与其父结点的位置,并将原目标结点的父结点当作新的目标结点继续进行向上调整。
  3. 若目标结点的值不大于其父结点的值,则停止向上调整,此时该树已经是大堆了。
void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType x = *p1;
	*p1 = *p2;
	*p2 = x;
}

// 除了child这个位置,前面数据构成堆
void AdjustUp(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;
	//while (parent >= 0)
	while(child > 0)
	{
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

堆的基本操作

定义堆

typedef int HPDataType;//堆中存储数据的类型

typedef struct Heap
{
	HPDataType* a;//用于存储数据的数组
	int size;//记录堆中已有元素个数
	int capacity;//记录堆的容量
}HP;

初始化堆

然后我们需要一个初始化函数,对刚创建的堆进行初始化,注意在初始化期间要将传入数据建堆。

//初始化堆
void HeapInit(HP* php, HPDataType* a, int n)
{
	assert(php);

	HPDataType* tmp = (HPDataType*)malloc(sizeof(HPDataType)*n);//申请一个堆结构
	if (tmp == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	php->a = tmp;
	memcpy(php->a, a, sizeof(HPDataType)*n);//拷贝数据到堆中
	php->size = n;
	php->capacity = n;
	int i = 0;
	//建堆
	for (i = (php->size - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(php->a, php->size, i);
	}
}

当然还有简化的版本

void HeapInit(HP* php)
{
	assert(php);

	php->a = (HPDataType*)malloc(sizeof(HPDataType)*4);
	if (php->a == NULL)
	{
		perror("malloc fail");
		return;
	}

	php->size = 0;
	php->capacity = 4;
}

 销毁堆

 为了避免内存泄漏,使用完动态开辟的内存空间后都要及时释放该空间,所以,一个用于释放内存空间的函数是必不可少的。

//销毁堆
void HeapDestroy(HP* php)
{
	assert(php);

	free(php->a);//释放动态开辟的数组
	php->a = NULL;//及时置空
	php->size = 0;//元素个数置0
	php->capacity = 0;//容量置0
}

打印堆

 打印堆中的数据,这里用了两种打印格式。第一种打印格式是按照堆的物理结构进行打印,即打印为一排连续的数字。第二种打印格式是按照堆的逻辑结构进行打印,即打印成树形结构。

//求结点数为n的二叉树的深度
int depth(int n)
{
	assert(n >= 0);

	if (n>0)
	{
		int m = 2;
		int hight = 1;
		while (m < n + 1)
		{
			m *= 2;
			hight++;
		}
		return hight;
	}
	else
	{
		return 0;
	}
}

//打印堆
void HeapPrint(HP* php)
{
	assert(php);
	//按照物理结构进行打印
	int i = 0;
	for (i = 0; i < php->size; i++)
	{
		printf("%d ", php->a[i]);
	}
	printf("\n");
	//按照树形结构进行打印
	int h = depth(php->size);
	int N = (int)pow(2, h) - 1;//与该二叉树深度相同的满二叉树的结点总数
	int space = N - 1;//记录每一行前面的空格数
	int row = 1;//当前打印的行数
	int pos = 0;//待打印数据的下标
	while (1)
	{
		//打印前面的空格
		int i = 0;
		for (i = 0; i < space; i++)
		{
			printf(" ");
		}
		//打印数据和间距
		int count = (int)pow(2, row - 1);//每一行的数字个数
		while (count--)//打印一行
		{
			printf("%02d", php->a[pos++]);//打印数据
			if (pos >= php->size)//数据打印完毕
			{
				printf("\n");
				return;
			}
			int distance = (space + 1) * 2;//两个数之间的空格数
			while (distance--)//打印两个数之间的空格
			{
				printf(" ");
			}
		}
		printf("\n");
		row++;
		space = space / 2 - 1;
	}
}

堆的插入

 数据插入时是插入到数组的末尾,即树形结构的最后一层的最后一个结点,所以插入数据后我们需要运用堆的向上调整算法对堆进行调整,使其在插入数据后仍然保持堆的结构。

void HeapPush(HP* php, HPDataType x)
{
	assert(php);

	if (php->size == php->capacity)
	{
		HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * php->capacity*2);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		php->a = tmp;
		php->capacity *= 2;
	}

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

	AdjustUp(php->a, php->size - 1);
}

 这个插入的效果完全取决于AdjustUp函数是给大堆设计的还是小堆!!

堆的删除

的向下调整算法思路主要涉及到在删除堆顶元素(最大或最小元素)后,从堆的最后一个元素开始,将其放到堆顶,并通过一系列的交换操作来重新维护堆的性质。这个算法在堆排序和优先队列等应用中非常关键。

大堆(Max Heap)的向下调整算法思路:

  1. 准备阶段
    • 假设堆中当前有 n 个元素,删除堆顶元素后,将最后一个元素(第 n 个元素)移动到堆顶位置。
    • 初始化当前节点 k 为堆顶节点(索引为 0 或 1,取决于实现)。
  2. 调整过程
    • 获取当前节点 k 的左右子节点的索引。
    • 比较当前节点 k 的值与左右子节点的值,找到三者中的最大值。
    • 如果最大值不是当前节点 k,则将其与最大值所在位置的节点交换。
    • 更新 k 为交换后的最大值所在位置的节点索引。
    • 重复上述步骤,直到 k 没有子节点或者 k 的值不小于其子节点的值,此时堆的性质得以恢复。

小堆(Min Heap)的向下调整算法思路:

  1. 准备阶段
    • 与大堆类似,删除堆顶元素后,将最后一个元素移动到堆顶位置。
    • 初始化当前节点 k 为堆顶节点。
  2. 调整过程
    • 获取当前节点 k 的左右子节点的索引。
    • 比较当前节点 k 的值与左右子节点的值,找到三者中的最小值。
    • 如果最小值不是当前节点 k,则将其与最小值所在位置的节点交换。
    • 更新 k 为交换后的最小值所在位置的节点索引。
    • 重复上述步骤,直到 k 没有子节点或者 k 的值不大于其子节点的值,此时堆的性质得以恢复。

关键点解释:

  • 子节点索引:对于数组实现的堆,可以通过 (k * 2 + 1) 和 (k * 2 + 2) 来获取当前节点 k 的左子节点和右子节点的索引(假设数组下标从 0 开始)。
  • 比较与交换:根据堆的性质(大堆或小堆),比较当前节点与其子节点的值,并根据需要进行交换,以保证堆的性质得以维持。
  • 终止条件:当当前节点 k 没有子节点(即 k 的索引超过了数组长度的一半减一),或者当前节点的值已经满足堆的性质(对于大堆是不小于子节点,对于小堆是不大于子节点)时,算法终止。

通过这种向下调整算法,可以在删除堆顶元素后快速恢复堆的性质,使得堆能够继续作为有效的数据结构进行后续操作。

//堆的删除
void HeapPop(HP* php)
{
	assert(php);
	assert(!HeapEmpty(php));

	Swap(&php->a[0], &php->a[php->size - 1]);//交换堆顶和最后一个结点的位置
	php->size--;//删除最后一个结点(也就是删除原来堆顶的元素)
	AdjustDown(php->a, php->size, 0);//向下调整
}

获取堆的数据个数

获取堆的数据个数,即返回堆结构体中的size变量。

//获取堆中数据个数
int HeapSize(HP* php)
{
	assert(php);

	return php->size;//返回堆中数据个数
}

堆的判空

堆的判空,即判断堆结构体中的size变量是否为0。文章来源地址https://www.toymoban.com/news/detail-861125.html

//堆的判空
bool HeapEmpty(HP* php)
{
	assert(php);

	return php->size == 0;//判断堆中数据是否为0
}

到了这里,关于堆的介绍,实现(c语言实现)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 【数据结构—二叉树的基础知识介绍和堆的实现(顺序表)】

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

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

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

    2023年04月19日
    浏览(53)
  • 初阶数据结构(五) 栈的介绍与实现

    💓博主csdn个人主页:小小unicorn💓 ⏩专栏分类:C++ 🚚代码仓库:小小unicorn的学习足迹🚚 🌹🌹🌹关注我带你学习编程知识 栈 :一种特殊的 线性表 ,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数

    2024年02月11日
    浏览(45)
  • 初阶数据结构(六)队列的介绍与实现

    💓博主csdn个人主页:小小unicorn💓 ⏩专栏分类:C++ 🚚代码仓库:小小unicorn的学习足迹🚚 🌹🌹🌹关注我带你学习编程知识 队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表。队列遵守先进先出FIFO(First In First Out)的原则。 入队列:队列的

    2024年02月11日
    浏览(41)
  • 【数据结构初阶】之堆(C语言实现)

    前言 :在二叉树基础篇我们提到了二叉树的顺序实现,今天让我们来学习一下特殊的二叉树———堆的相关知识。 📃 博客主页: 小镇敲码人 💞 热门专栏:数据结构与算法 🚀 欢迎关注:👍点赞 👂🏽留言 😍收藏 🌏 任尔江湖满血骨,我自踏雪寻梅香。 万千浮云遮碧月

    2024年04月09日
    浏览(82)
  • 数据结构初阶(用C语言实现简单数据结构)--栈和队列

    ✨✨欢迎来到T_X_Parallel的博客!!       🛰️博客主页:T_X_Parallel       🛰️专栏 : 数据结构初阶       🛰️欢迎关注:👍点赞🙌收藏✍️留言 这小猫真好看 言归正传,通过上篇有关顺序表和链表的博客,可以了解到线性表的一些大致特征,这篇博

    2024年02月08日
    浏览(42)
  • 数据结构初阶之顺序表(C语言实现)

    顺序表是数据结构里面很基础的一类,它是线性表的一种,其它线性表还有链表、栈和队列等,今天来和博主一起学习关于顺序表的知识吧。 顺序表,它分为两类: 动态顺序表 和 静态顺序表 ,这两个表的区别就是 前者的空间不固定 ,是 支持扩容 的,后者的 空间是固定

    2024年02月03日
    浏览(45)
  • C语言数据结构初阶(10)----二叉树的实现

    · CSDN的uu们,大家好。这里是C语言数据结构的第十讲。 · 目标:前路坎坷,披荆斩棘,扶摇直上。 · 博客主页: @姬如祎 · 收录专栏: 数据结构与算法     目录 1. 函数接口一览 2. 函数接口的实现 2.1 BTNode* BuyNode(BTDataType x) 的实现 2.2 BTNode* CreateTree() 的实现  2.3 void

    2023年04月08日
    浏览(44)
  • Leetcode刷题---C语言实现初阶数据结构---单链表

    删除链表中等于给定值 val 的所有节点 给你一个链表的头节点head和一个整数val,请你删除链表中所有满足Node.val==val的节点,并返回新的头节点 输入:head = [1,2,6,3,4,5,6], val = 6 输出:[1,2,3,4,5] 示例 2: 输入:head = [ ], val = 1 输出:[ ] 示例 3: 输入:head = [7,7,7,7], val = 7 输出:

    2024年02月15日
    浏览(57)
  • 数据结构初阶之基础二叉树(C语言实现)

    📃 博客主页: 小镇敲码人 💞 热门专栏:数据结构与算法 🚀 欢迎关注:👍点赞 👂🏽留言 😍收藏 🌏 任尔江湖满血骨,我自踏雪寻梅香。 万千浮云遮碧月,独傲天下百坚强。 男儿应有龙腾志,盖世一意转洪荒。 莫使此生无痕度,终归人间一捧黄。🍎🍎🍎 ❤️ 什么

    2024年03月19日
    浏览(43)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包