2023面试高手

这个屌丝很懒，什么也没留下！

热门标签

数据结构——堆的定义，堆的数据操作函数以及堆对数组的排序知识点详解！！

作者：2023面试高手 | 2024-05-24 20:08:21

踩

引言：这篇博客中将会讲到二叉树的具体应用——堆。堆是一种以二叉树概念为基础，数组为存储结构的数据结构，相较于我们之前学到的数据结构来说，堆的难度更大，当然，堆的效率也就更高！最后，我们还将会使用堆的思想来实现一个对数组进行排序的函数（强大到排序含上千万个元素的数组都不在话下）。当然，想要学会堆，则需要建立在搞懂了二叉树的基础上。好好看，好好学，读懂这篇博客，我们一起拿下数据结构——堆！

更多有关C语言和数据结构知识详解可前往个人主页：计信猫

一，堆的含义

首先，堆一定是一棵二叉树，然后，在此基础上，堆就可以分为大堆和小堆。

大堆：任何一个父节点所储存的值都大于等于其子节点所储存的值。

小堆：任何一个父节点所储存的值都小于等于其子节点所储存的值。

堆的特点：堆的根节点所储存的值一定是堆的最小值或者最大值。

但是我们一定不可以搞混的一点就是：大堆不一定是降序排列，小堆不一定是升序排列！因为堆中并未规定兄弟节点的大小关系。

二，堆的结构体的定义

老样子，三文件操作法走你！分别创建Heap.h、Heap.c、test.c三个文件。

就像前文提到的，堆是一种以二叉树概念为基础，数组为存储结构的数据结构，所以我们定义堆结构体的方法就与定义顺序表的方法十分相似，于是我们在Heap.h头文件中做如下定义，如下所示：


//包含会用到的头文件
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef int HPDataType;
typedef struct Heap
{
	int* a;//用于储存堆的数组
	int size;//指向最后一个元素的下一位
	int capacity;//数组空间总大小
}HP;

三，堆的数据操作函数

相信有了之前对数据结构操作函数的学习之后，关于一些数据操作函数代码的编写一定对我们都不在话下了，所以我将略讲部分我们熟悉的函数，但细讲我们新学到的函数。

而在接下来的代码演示中我都将以小堆为例子进行代码的编写，大堆的代码与小堆十分相似。如果听懂了小堆的数据操作代码，那么编写大堆的数据操作代码也就易如反掌了。

1，堆的初始化


//堆的初始化
void HPInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->size = php->capacity = 0;
}

2，堆的销毁


//堆的销毁
void HPDestroy(HP* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->size = php->capacity = 0;
}

3，堆的插入数据

那么对于堆的插入数据函数，就开始上强度了。首先我们看一张图：

如图，这是一张在小堆中插入元素10的操作图。当我们插入元素10在小堆尾部之后，会发现小堆的结构就被破坏了，形成的新树不满足小堆的要求了。所以此时我们就需要对元素10进行向上遍历，使元素10到达堆中自己应该在的位置。

那我们如何向上遍历呢？其实很简单。如下图所示：

我们将10的节点定义为子节点（child），那么它的父节点（parent）就可以通过公式找到parent=（child-1）/2。然后我们对两节点最储存的值进行大小判断，如果子节点的值更大，那么就跳出遍历循环，如果父节点的值更大，那我们就将两节点的值进行交换，之后再重新赋值子节点并找到其对应的父节点。重复以上操作即可。

所以有了以上的理论支持之后，我们就可以定义一个向上遍历函数AdjustUp和数据交换函数swap:


//交换函数
void swap(int* child, int* parent)
{
	int temp = *child;
	*child = *parent;
	*parent = temp;
}
//向上遍历函数
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 = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

有了这个函数之后，我们再进行元素的插入之后，我们就可以调用AdjustUp函数，将新堆重新变为原来的小堆。所以我们的堆的数据插入函数如下：


//堆的数据插入函数
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 fail!");
			return;
		}
		php->a = tmp;
		php->capacity = newcapacity;
	}
	php->a[php->size - 1] = x;
	php->size++;
    //向上遍历堆
	AdjustUp(php->a, php->size - 1);
}

4，堆的删除数据

该函数是第二个难点，但其实也跟堆的数据插入函数也没什么两样。

首先我们需要明白，我们堆的数据删除函数是对堆顶部的数据进行删除。假如我们想删除如下图堆的数据：

那么，想要对堆的顶部数据进行删除，我们就可以使用如下方式：

首先，我们将堆的最后一位数据与根数据进行交换。

然后我们再对size进行减减操作，使节点15被删去。

最后，我们再将现在新的堆顶进行向下遍历，使这个堆重新变为一个小堆。

那么，现在思路明确了，新的问题就来了，我们应该如何写代码，才可以达到让堆顶元素向下遍历的效果呢？

其实也不难，我们开始讲解操作：首先我们可以很简单的找到根节点的下标，也就是0。那么如果我们想要向下遍历的话，我们就应该让根节点的子节点的较小值与根节点交换位置，如下图所示：

那么我们如何找到根节点的两个子节点的较小值呢？那我们就可以使用我们之前使用过的假设法。


//假设法,我们先假设左孩子为较小节点
	int child = parent * 2 + 1;
	//child+1<n是为了保证右孩子的存在
	if (child + 1 < n && a[child + 1] < a[child]);
	{
		//右孩子存在且更小，所以右孩子的下标为child
		child = child + 1;
	}

既然现在我们找到了更小的孩子，所以接下来我们就应该将两节点交换位置，并且重新对新的parent节点和child节点赋值。

并且如此循环往复，就可以实现根节点的向下遍历了！代码如下：


//向下遍历函数
void AdjustDown(HPDataType* a, int n, int parent)
{
	//假设法,我们先假设左孩子为较小节点
	int child = parent * 2 + 1;
	while (child < n)//child>=n说明孩子不存在，走到了叶节点了
	{
	//child+1<n是为了保证右孩子的存在
		if (child + 1 < n && a[child + 1] < a[child]);
		{
			//右孩子存在且更小，所以右孩子的下标为child
			child = child + 1;
		}
		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 > 0);
	//将堆的根节点与最后一个节点进行交换
	swap(php->a[php->size - 1], php->a[0]);
	//再删去最后一个节点
	php->size--;
	//最后进行向下遍历，使新的堆重新成为小堆
	AdjustDown(php->a, php->size, 0);
}

5，判断堆的判空

关于堆的判空函数则十分简单，我们只需要判断size是否为零就可以了，所以我们直接上代码！


//堆的判空
bool HPEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}

6，取堆顶元素

这也是我们在堆的数据操作函数中所需要学到的最后一个函数，极其简单，我们直接上代码吧！


//取堆顶元素
HPDataType HPTop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	return php->a[0];
}

四，堆的数组排序

接下来我们所讲到的数组排序，将仍会有一些难度，希望大家可以认真看，好好理解，如果有不懂的地方可以私信和我交流！

0，准备

在这里，我们将前面所学到的AdjustUp和AdjustDown函数进行细分，将他们分别分为两种不同的建堆方式——AdjustUpBig（用于建大堆的向上遍历函数）/AdjustUpSmall（用于建小堆的向上遍历函数）与AdjustDownBig（用于建大堆的向下遍历函数）/AdjustDownSmall（用于建小堆的向下遍历函数）。而他们的不同之处其实也就仅仅在于大于小于符号的改变而已。

建小堆：


//建小堆向上遍历函数
void AdjustUpSmall(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 = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
//建小堆向下遍历函数
void AdjustDownSmall(HPDataType* a, int n, int parent)
{
	//假设法,我们先假设左孩子为较小节点
	int child = parent * 2 + 1;
	while (child < n)//child>=n说明孩子不存在，走到了叶节点了
	{
	//child+1<n是为了保证右孩子的存在
		if (child + 1 < n && a[child + 1] < a[child])
		{
			//右孩子存在且更小，所以右孩子的下标为child
			child = child + 1;
		}
		if (a[child] < a[parent])
		{
			//交换父节点和子节点
			swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

建大堆：


//建大堆向上遍历函数
void AdjustUpBig(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 = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
//建大堆向下遍历函数
void AdjustDownBig(HPDataType* a, int n, int parent)
{
	//假设法,我们先假设左孩子为较小节点
	int child = parent * 2 + 1;
	while (child < n)//child>=n说明孩子不存在，走到了叶节点了
	{
		//child+1<n是为了保证右孩子的存在
		if (child + 1 < n && a[child + 1] > a[child])
		{
			//右孩子存在且更大，所以右孩子的下标为child
			child = child + 1;
		}
		if (a[child] > a[parent])
		{
			//交换父节点和子节点
			swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

那么，假如说我们拿到如下的一个数组，我们将怎样对它进行降序（升序）排序呢？

此处我们以降序排序为例子。

1，建大堆还是小堆

首先我们拿到一个数组，我们就可以先将这个数组建成一个堆，再进行操作。但是这时候问题就来了，我们应该将数组建成一个大堆还是小堆呢？

这时候一些朋友可能就会说：既然我们要进行降序排列，那我们肯定是建大堆更好啊，毕竟第一个最大的数就已经给你排在数组第一位了。那么我们就先使用大堆进行排序吧，将如上例子进行大堆排序后，我们就会得到以下结果：

由此可见，最大的一位9确实就进入了数组的第一位。 但是此时此刻问题就出现了，那我们如何找出第二大的数呢？那我们就不得不再将数组的第一位暂时忽略，然后将数组的后7位重新建堆，继续找出第二大的数了，这样循环往复，找一个数就使用循环建一次大堆，则会导致我们算法的时间复杂度过高。

所以，在此时我们便可以采用建小堆的方法。假如我们先创建出小堆，如下图所示：

建成小堆之后，我们就找到了数组中最小的元素，那此时我们就将最小的元素和最后一个元素交换位置，此时最小的元素不就进入数组的末尾了吗？如下：

而这样做的好处就是，这个新的堆只需要将根元素遍历一次就可以又一次形成小堆了。大大节省了算法的时间复杂度！！

所以我们得出结论：

●排列降序数组，建小堆
●排列升序数组，建大堆

2，如何建堆

那么此时此刻，关于建堆就有两种方式了：一，向上遍历法。二，向下遍历法。

Ⅰ ，向上遍历法

该方法其实就是使用我们前面提到的AdjustUp类的函数来进行循环建堆，我们将数组的单个元素就看成一个堆，那么我们的循环就从数组下标为1的地方开始进行向上遍历。代码如下：


	int arr[] = { 4,2,8,1,5,6,9,7};
	for (int i = 0; i < sizeof(arr)/sizeof(arr[0]); i++)
	{
		AdjustUpSmall(arr, i);
	}

Ⅱ ，向下遍历法

向下遍历法其实就比较难理解，但是向下遍历法有着比向上遍历法更高的效率。首先我们可以将单个叶节点视为一个堆，然后我们就从倒数第一个非叶子节点进行向下遍历。如下图所示：

所以，我们依次地向上走，并同时使用向下遍历法，就可以保证每一次遍历之前的子树一定是大堆或小堆。（这里我们以小堆为例子）


	int n = sizeof(arr) / sizeof(arr[0]);
	for (i = (n - 1 - 1) / 2/*找出子节点的父节点*/; i >= 0; i--)
	{
		//向下遍历法
		AdjustDownSmall(arr, n,i);
	}

3，如何排序

这个问题其实我在前面就已经讲过，并分析了利弊了，所以在这里我们就是用前面提到的方法。

●排降序，建小堆。排序时每次循环都将第一个元素和最后一个元素互换位置，然后进行向下调整，最后再将最后一个元素忽略。
	int end = n - 1;//n为数组总大小
	while (end > 0)
	{
		//交换根节点和最后一个节点
		swap(&arr[0], &arr[end]);
		//向下调整
		AdjustDownSmall(arr, end, 0);
		//忽略最后一个节点
		end--;
	}
●排升序，建大堆。排序时每次循环都将第一个元素和最后一个元素互换位置，然后进行向下调整，最后再将最后一个元素忽略。
int end = n - 1;//n为数组总大小
	while (end > 0)
	{
		//交换根节点和最后一个节点
		swap(&arr[0], &arr[end]);
		//向下调整
		AdjustDownBig(arr, end, 0);
		//忽略最后一个节点
		end--;
	}

4，排序代码总结

使用大堆排升序数组：


//数组升序排序
void HPUpSort(HPDataType* a, int n)
{
	//使用向下遍历法建大堆
	for (int i = (n-1-1) / 2; i >= 0; i--)
	{
		AdjustDownBig(a, n, i);
	}
	int end = n - 1;
	while (end > 0)
	{
		//交换根节点和最后一个节点
		swap(&a[0], &a[end]);
		//向下调整
		AdjustDownBig(a, end, 0);
		//忽略最后一个节点
		end--;
	}
}

使用小堆排降序数组：


//数组降序排序
void HPDownSort(HPDataType* a, int n)
{
	//使用向下遍历法建小堆
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDownSmall(a, n, i);
	}
	int end = n - 1;
	while (end > 0)
	{
		//交换根节点和最后一个节点
		swap(&a[0], &a[end]);
		//向下调整
		AdjustDownSmall(a, end, 0);
		//忽略最后一个节点
		end--;
	}
}

五，结语

这篇文章虽然在我写的数据结构类的文章中字数不算最多的，但是却一定是最难的。在写数组排序这一块内容的时候，因为怕自己没办法讲清楚这个知识点，甚至又回去将课程学习了一遍，才完全搞懂了这个知识点。

刚开始学这个部分的你们相信也会感到很疑惑，但是解决了疑惑，那么你将迎来的就是进步和成就感。能顺利的解决堆排序问题，我感到很快乐和放松，在我写结语时，一想到又将一个知识点清楚的写在了博客上就感到成就感满满。

让我们共同加油，一起进步！！

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/2023面试高手/article/detail/618929

数据结构——堆的定义，堆的数据操作函数以及堆对数组的排序知识点详解！！

一，堆的含义

二，堆的结构体的定义

三，堆的数据操作函数

1，堆的初始化

2，堆的销毁

3，堆的插入数据

4，堆的删除数据

5，判断堆的判空

6，取堆顶元素

四，堆的数组排序

0，准备

1，建大堆还是小堆

2，如何建堆

Ⅰ ，向上遍历法

Ⅱ ，向下遍历法

3， 如何排序

4，排序代码总结

五，结语

3，如何排序