【数据结构】堆

博主的博客个人主页~
博主的数据结构专栏~

上期博客我们介绍了树，本期我们来实现一种特殊的二叉树—堆。上期博客，食用请点击~

一、堆

1.1 堆的概念与存储结构

堆是一种特殊的完全二叉树数据结构，堆分为大根堆(大顶堆)和小根堆(小顶堆)，在大根堆中，每个节点的值都大于或等于其左右子节点的值；在小根堆中每个节点的值都小于或等于其左右节点的值。


完全二叉树适合用数组存储，它的节点排列非常规律，除最后一层外，每一层都是满的，且最后一层节点靠左对齐，用数组储存时，可根据根节点在数中的位置与数组下标的对应关系进行高效的访问和操作。因此我们将用数组来实现堆这一数据结构。

堆的性质：

• 堆中某个结点的值总是不大于或不小于其父结点的值；
• 堆总是⼀棵完全二叉树。
  完全二叉树的性质：
  对于具有 n 个结点的完全二叉树，如果按照从上到下从左到右的数组顺序对所有结点从0 开始编号，则对于序号为 i 的结点有：
• 若 i>0，i 位置结点的双亲序号：(i-1)/2 ；若i=0，i 为根结点编号，无双亲结点。
• 若 2i+1<n，左孩子序号： 2i+1；若2i+1>=n 无左孩子。
• 若 2i+2<n，右孩子序号： 2i+2；若2i+2>=n 无右孩子。

以上性质十分重要，只有知道以上性质我们才能操作实现堆。(以上性质读者可以通过上面给出的两幅图来验证，如有疑问，请在评论区留言。)

二、堆的实现

2.1 堆的结构定义

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* arr;
	int size;    //有效数据个数
	int capacity;//容量大小
}HP;

由于使用数组实现堆，所以我们这边需要知道数组中存放了多少的有效数据size和数组的容量大小capacity，它的结构和顺序表的结构相似。

2.2 堆的初始化与销毁

由于初始化和销毁和顺序表的方式相同，所以我们就直接给出代码了，关于顺序表读者可以点击这个观看：【数据结构】顺序表
初始化：

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

销毁：

void HPDestroy(HP* php)
{
	if (php->arr)
	{
		free(php->arr);
	}
	php->arr = NULL;
	php->size = php->capacity = 0;
}

2.3 堆的打印

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

2.4堆的插入

在插入的实现过程中，第一个要考虑的问题就是数组的容量满了没有，如果满了，我们要增容，所以我们首先会判断容量够不够的问题，其次，堆这一数据结构，不像顺序表，它判断增不增容后，将数据往后一插就可以了，但堆它分为大根堆和小根堆，所以我们插入之后，如果不合适的话，还要调整数据的位置，来保证我们建的堆始终是大根堆或者小根堆。那么应该如何调整呢？

我们以下面这幅图为例：：

我们接下来要插入一个数字99，很明显它比里面的所有数字都要大，但它现在在堆的末尾，所以，我们要将它向上调整(即使我们建的是小根堆也一样，如果插入的数据比其他数据要小，我们依旧要向上调整)。我们知道通过孩子节点可以找到父节点，假设孩子节点为i，那么父节点为(i-1)/2。

上图就是向上调整的过程图，由于我们插入的是之前调整好的堆，所以我们只需要将新插入的和父节点比较即可。在代码实现过程中我会将交换和向上调整操作单独封装成函数。

我们将以创建大根堆为示范：

void HPPush(HP* php, HPDataType x)
{
	assert(php);
	if (php->size == php->capacity)
	{
		int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
		HPDataType* set =(HPDataType*)realloc(php>arr,2*newcapacity*sizeof(HPDataType));
		if (set == NULL)
		{
			perror("realloc fail!");
			return 1;
		}
		php->arr = set;
		php->capacity = newcapacity;
	}
	php->arr[php->size] = x;
	AdjustUp(php->arr, php->size);
	php->size++;
}

向上调整：

void AdjustUp(HPDataType* arr, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (arr[child] > arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
			break;
	}
}

交换：

void Swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

测试代码：

#include "Heap.h"

void test()
{
	HP hp;
	HPInit(&hp);
	HPPush(&hp, 10);
	HPPush(&hp, 20);
	HPPush(&hp, 30);
	HPPush(&hp, 40);
	HPPush(&hp, 50);
	HPPush(&hp, 70);
	HPPrint(&hp);
}

int main()
{
	test();
	return 0;
}

测试结果：

还原成堆：

可以看出，依旧是大根堆。

2.5 堆的删除

在堆结构中删除数据只能删除堆顶，我们不能直接将堆顶删除，不然的话就不是堆结构了，它成为了两个子树，所以我们在删除的时候，要先将最后一个元素和堆顶交换位置，之后有效数据个数size减一，即可删除堆顶元素，但此时操作依旧没有结束，因为经过我们的交换操作，我们建立的大根堆(小根堆)已经不是大根堆(小根堆)了，所以我们依旧要对其进行调整，只不过这次是向下调整，另外我们还要判断删除操作时堆结构是否为空。

我们以一下这幅图为例：

调整过程：

判空函数：

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

向下调整算法：

//向下调整
void AdjustDown(HPDataType* arr, int parent, int n)
{
	//假设左孩子大
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && arr[child] < arr[child + 1])
		{
			child++;
		}
		if (arr[child] > arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

堆的删除：

//堆的删除
void HPPop(HP* php)
{
	assert(!HPEmpty(php));
	Swap(&php->arr[0], &php->arr[php->size - 1]);
	php->size--;
	AdjustDown(php->arr, 0, php->size);
}

测试代码：

#include "Heap.h"

void test()
{
	HP hp;
	HPInit(&hp);
	HPPush(&hp, 10);
	HPPush(&hp, 20);
	HPPush(&hp, 30);
	HPPush(&hp, 40);
	HPPush(&hp, 50);
	HPPush(&hp, 70);
	HPPrint(&hp);
	HPPop(&hp);
	HPPop(&hp);
	HPPop(&hp);
	HPPrint(&hp);
}

int main()
{
	test();
	return 0;
}

测试结果：

还原成子树：

2.6 取堆顶数据

//取堆顶数据
HPDataType HPTop(HP* php)
{
	assert(!HPEmpty(php));
	return php->arr[0];
}

2.7求有效数据个数size

//求有效数据个数size
int HPSize(HP* php)
{
	assert(php);
	return php->size;
}

总结：
以上就是本期博客分享的全部内容啦！如果觉得文章还不错的话可以三连支持一下，你的支持就是我前进最大的动力！
技术的探索永无止境! 道阻且长，行则将至！后续我会给大家带来更多优质博客内容，欢迎关注我的CSDN账号，我们一同成长！
(～￣▽￣)～