【初阶数据结构】森林里的树影 “堆” 光：堆

初步了解了关于树型结构的知识与结构后，堆的功能实现能帮我们学会一种排序——堆排序，二叉树也是很重要的一种文件式的结构

在学习本专题前，请详细学习有关树的知识与结构

传送门：【初阶数据结构】树型数据的勘探：树

堆的概念及结构

如果有一个关键码的集合 K = {$k_0$，$k_1$， $k_2$，…，$k_{n-1}$}，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：$K_i$ <= $K_{2i+1}$ 且 $K_i$<= $K_{2*i+2}$ ($K_i$ >= $K_{2i+1}$ 且 $K_i$ >= $K_{2*i+2}$) i = 0，1，2…，则称为小堆(或大堆)。将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆

堆的性质：

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

🚩堆总是一棵完全二叉树

堆的结构：

typedef int HPDataType;

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

堆的本质就是一个动态数组，把数组以堆的形式呈现出来而已，所以在实现堆的功能时要多画图来帮助理解

堆的接口实现

堆的初始化

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;
}

熟悉的初始化配方：

1. 判断是否为空指针
2. 创建空间，注意是否会因为开辟失败造成空指针
3. 初始化变量 size 和 capacity

🔥值得注意的是： 参数的指针浅拷贝，指向同一块空间，能够改变该空间里的内容，不涉及改变原空间的地址，所以传一级指针即可

堆的销毁

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

	free(php->a);
	php->a = NULL;
	php->capacity = php->size = 0;
}

堆的交换

void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

因为在堆调整中涉及多次的节点交换，所以额外写一个 Swap 交换函数方便使用

堆的向上调整

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;
		}
	}
}

向上调整通常用于最大堆的调整

当向最大堆中插入一个新元素时，新元素会被放置在堆的末尾（即数组的最后一个位置），此时可能会破坏堆的性质（最大堆要求每个节点的值都大于或等于其子节点的值）

通过调用 AdjustUp 函数，可以将新插入的元素上浮到合适的位置，使得整个堆重新满足最大堆的性质

🔥值得注意的是：

1. 无论是左节点还是右节点，父亲节点的索引可以通过 (child - 1) / 2 计算得出
2. while 循环的条件 child > 0 不能写成 child >= 0。当 child 等于 0 时，表示已经到达堆顶，按照 parent = (child - 1) / 2 计算，(-1) / 2 结果为 0（整数除法向下取整），这会导致 parent 和 child 相等，无法向上调整，陷入类似死循环的效果
3. 除了 child 这个数据，前面的数据构成堆，因为向上调整的前提是其他数据都成堆

堆的插入

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

	php->a[php->size] = x;
	AdjustUp(php->a, php->size);
	php->size++;
}

实现了向上调整，那么插入就很容易了，检查容量是否足够插入，调整新插入的数据也构成堆即可

🔥值得注意的是： 不是 php->capacity * 2 ，而是 php->capacity * 2 * sizeof(HPDataType)，注意是字节数不是容量数

堆的向下调整

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;
		}
	}
}

向下调整通常用于最小堆的调整（这里写的是最大堆的调整）

向下调整的前提是左右子树都必须是大堆或者小堆

🔥值得注意的是：

1. 必须把大的那个孩子往上调，保证大堆的性质
2. 这里假设子节点中的左孩子 child = parent * 2 + 1 是子节点中最大的
3. child + 1 < n && a[child + 1] > a[child] 的目的是判断是否存在右子节点，如果存在，再判断左子节点是否大于右子节点，如果大于就交换
4. 不能写成 a[child + 1] > a[child] && child + 1 < n，要先判断是否存在再访问，不然就非法越界了

堆的删除

在写堆删除代码前，我们要思考一个问题：

为什么不用像之前顺序表那样常用的删除方法——后一个覆盖前一个？

比如一个数组 {42，12，18，4，2，3}

如果采用后一个覆盖前一个的方法删除节点：

1. 向下调整的效率是 O($log_n$) ，后一个覆盖前一个的效率是 O(n) ，假设需要挪动100万次，那么向下调整只需最多20次就能解决，这效率翻得可不止一倍两倍
2. 后一个覆盖前一个之后父子关系全乱，无法进行堆调整

删除堆通常是删除堆顶的数据，将堆顶的数据和最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法

那么为什么是采用最后一个叶节点和根节点交换？

画图可以发现这种交换方式，不会太大程度上破坏堆的结构，保证能够进行向下调整来恢复堆的秩序

🔥值得注意的是： 删除特定位置元素的方法和删除堆顶是一样的

1. 遍历整个堆来找到目标元素位置
2. 将目标位置的元素与堆的最后一个元素进行交换
3. 根据交换后该元素的值与周围元素的大小关系，决定是进行上浮操作还是下沉操作来恢复堆的性质

因此删除堆的代码也能轻松写出来：

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);
}

堆顶获取

HPDataType HeapTop(HP* php)
{
	assert(php);
	return php->a[0];
}

返回堆顶元素的值，最大堆的堆顶元素是堆中的最大值，最小堆的堆顶元素是堆中的最小值

堆的判空

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

如果 php->size 等于 0，说明堆中没有元素，函数返回 true；否则返回 false

堆的节点个数

int HeapSize(HP* php)
{
	assert(php);
	return php->size;
}

设置一个返回 size 的函数方便获取堆的节点个数，否则获取 size 只能通过遍历

堆的打印

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

堆的排序（向上建堆）

既然堆有调整大小顺序的性质，那么就可以据此实现排序的功能

我们知道无论是向上调整，还是向下调整，都要基于一个具有完整性质的堆下来实现，分为向上建堆和向下建堆

向上建堆：

向上建堆的核心思想是逐个插入元素到堆中，每插入一个元素就对其进行向上调整操作，使其满足堆的性质。具体来说，从数组的第一个元素开始，依次将每个元素插入到已经构建好的部分堆中，然后通过上浮操作将该元素调整到合适的位置，确保整个数组始终保持堆的性质。其实就是对堆插入的模拟实现

建好堆之后，就能对堆进行排序，排序分为升序和降序

• 升序：建大堆
• 降序：建小堆

为什么排序是这样建堆呢？

假设我们要实现升序，如果是建小堆的话，最小值就放在最上面不能动了，剩下的数如果想排序那又得看成一个堆，但是这样父子关系全乱了，因此每排好一个数就要重新建堆，那么效率就太低了。

实现升序就要考虑建大堆，然后再模拟堆删除的方式，不断把大的值调到最下面，最上面小的值通过向下调整，把堆调整为正常的大堆，保证左右子树都是大堆。此时最大的值又在最顶上，--end，和倒数第二个节点交换，重复上面的操作，循环往复就能实现排序

因此排序的代码为：

void HeapSort(HPDataType* a, int n)
{
	//向上调整建堆,i是下标,n是个数,a是数组 -- O(N * log N)
	for (int i = 0; i < n; ++i)
	{
		AdjustUp(a, i);
	}
	
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[end], &a[0]);
		AdjustDown(a, end, 0);
		--end;
	}
}

2.13 堆的排序（向下建堆）

向下建堆：

向下建堆的过程可以看作是一种分治策略，将一个大问题分解为多个小问题。向下建堆的核心思想是从最后一个非叶子节点开始，依次对每个非叶子节点进行向下调整（下沉）操作，使得以该节点为根的子树满足堆的性质，最终整个数组构成一个堆。简单来说就是对下面每一个小堆依次调整，最终整体就形成了一个大堆

假设有个数组{2，1，5，7，6，8，0，9，4，3}，要实现升序建大堆

1. 先从 6 这个堆开始调整
2. 然后按数组顺序往前推，调整 7 这个堆
3. 依次往前推对每个堆调整，最终就建成了一个大堆

建好之后，排序的方法和向上建堆是一样的

因此排序的代码为：

void HeapSort(HPDataType* a, int n)
{
	//向下调整建堆 -- O(N)
    //n-1是最后一个节点，(n-1-1)/2是最后一个节点的父节点
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(a, n, i);
	}

	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[end], &a[0]);
		AdjustDown(a, end, 0);
		--end;
	}
}

堆排序效率比较

向下建堆：

因此：向下建堆的时间复杂度为O(N)

用同样的方法，也能算出向上建堆的时间复杂度为O(N * log N)

所以向下建堆是更高效的

代码展示

传送门：Gitee堆代码

Heap.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>

typedef int HPDataType;

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

void HeapInit(HP* php);

void HeapDestroy(HP* php);

void Swap(HPDataType* p1, HPDataType* p2);

void AdjustUp(HPDataType* a, int child);

void AdjustDown(HPDataType* a, int n, int parent);

void HeapPush(HP* php, HPDataType x);

void HeapPop(HP* php);

HPDataType HeapTop(HP* php);

bool HeapEmpty(HP* php);

int HeapSize(HP* php);

void HeapPrint(HP* php);

void HeapSort(HPDataType* a, int n);

Heap.c

#define _CRT_SECURE_NO_WARNINGS

#include "Heap.h"

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->capacity = php->size = 0;
}

void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

//除了child这个数据，前面的数据构成堆
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;
		}
	}
}

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

	php->a[php->size] = x;
	AdjustUp(php->a, php->size);
	php->size++;
}

//左右子树都必须是大堆或者小堆
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;
		}
	}
}

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);
}

HPDataType HeapTop(HP* php)
{
	assert(php);
	return php->a[0];
}

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

int HeapSize(HP* php)
{
	assert(php);
	return php->size;
}

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

void HeapSort(HPDataType* a, int n)
{
	//向上调整建堆,i是下标，n是个数 -- O(N * log N)
	for (int i = 0; i < n; ++i)
	{
		AdjustUp(a, i);
	}

	/*向下调整建堆 -- O(N)
    n-1是最后一个节点，(n-1-1)/2是最后一个节点的父节点*/
	/*for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(a, n, i);
	}*/

	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[end], &a[0]);
		AdjustDown(a, end, 0);
		--end;
	}
}

---

希望读者们多多三连支持

小编会继续更新

你们的鼓励就是我前进的动力！