数据结构与算法：堆

---

堆

堆的定义

定义：

堆是一种数据结构，本质上是一个特殊的树结构，它是一个完全二叉树，其中每个节点的值都大于等于其子节点的值（对于大堆）或者小于等于其子节点的值（对于小堆）。

根据以上定义，一个数据结构可以称为堆有两个条件：

• 是一颗完全二叉树
• 每个父节点的值大于其子节点的值 或 每个父节点的值大于其子节点的值

其中，每个父节点的值大于其子节点的值称为大堆，每个父节点的值小于其子节点的值称为小堆。

以下就是一个大堆：

由于堆具有一定的规律，所以比一般的二叉树更有实际意义，比如堆排序以及TopK问题。

---

堆的实现

结构分析

堆一般用顺序表或数组来实现，那么一个树状结构要如何放到线性表或数组中呢？
一般而言，我们的处理方式是对树进行层序遍历，将每一层按顺序放到线性结构中，如下：

后续我们的实现堆，也是通过顺序表的结构，因为这一种结构更常见，实际意义也更高。但是在分析问题是，利用树结构会更加直观。

基本结构：

typedef int HPDataType;

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

这段代码定义了一个小堆。下面对每一行代码进行详细解析：

typedef int HPDataType;

这行代码定义了一个名为HPDataType的新类型，它是int类型的别名。这个别名将用于定义堆中的元素的类型，当后续需要用堆存储其它数据类型时，直接在此处修改即可。

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

这行代码定义了一个名为Heap的结构体类型，同时给这个结构体类型起了一个别名HP。Heap结构体包含了三个成员变量：

• a是指向HPDataType类型的指针，它将用于存储堆的元素。
• size表示当前堆中的元素个数。
• capacity表示堆的最大容量，即可以容纳的元素个数的上限。

这个结构体定义了一个数据结构，其中元素的类型为HPDataType。

综上所述，这段代码定义了一个名为HP的最小堆数据结构，其中堆的元素类型为HPDataType，堆的元素存储在数组a中，堆的当前元素个数存储在size中，堆的最大容量存储在capacity中。

---

初始化

//初始化
void HeapInit(HP* php)
{
	assert(php);

	php->a = NULL;
	php->size = 0;
	php->capacity = 0;
}

这段代码定义了一个名为HeapInit的函数，该函数的参数是一个指向HP类型的指针。

函数开始使用assert宏来确保传入的指针不为空，如果为空则会终止程序运行。

接着，函数通过指针php来访问HP结构体的成员变量。

首先，将php->a设置为NULL，表示堆中的元素数组为空。

---

然后，将php->size设置为0，表示堆中当前元素个数为0。

---

最后，将php->capacity设置为0，表示堆的容量为0，意味着还没有分配内存空间。

因此，这段代码的作用是初始化一个堆，将堆的元素数组指针设为NULL，元素个数和容量都设为0。这种初始状态的堆是一个空堆，没有任何元素。

---

在讲解堆的其它操作之前，要先讲解堆的最重要的两个算法，这两个算法可以维持堆的有序性。

向上调整算法

现在假设我有以下堆结构：

我现在在堆尾部插入一个数据，如何将数据调整到合适的位置，保证这个结构依然满足堆的要求？

想要将其插入到指定位置，就要使用到向上调整算法：将最后一个节点向上调整到合适的位置。

首先讲解一个公式：堆结构中父节点与子节点的下标关系

假设父节点的下标为parent，则其左子节点的下标为 2 * parent+1，右子节点的下标为 2 * parent+2。

由于大堆要保证每隔父亲节点大于两个子节点，而除去最后一个节点，其它的节点已经满足堆结构了，所以此处需要将最后一个节点不断地与其父亲节点比较，如果其比父亲节点大，就交换位置，然后继续和新的父亲节点比较，直到比当前的父亲节点小，或者到达堆顶为止。

图示：

在顺序表中的效果（实际效果）：

代码实现：

//向上调整
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. 函数定义：

void AdjustUp(HPDataType* a, int child)

该函数接受两个参数：指向数组的指针a和待调整元素的索引child。HPDataType是堆中存储的元素类型。

2. 定义父节点索引：

int parent = (child - 1) / 2;

根据完全二叉树的性质，节点i的父节点索引是(i - 1) / 2，所以计算出child节点的父节点索引。

3. 进入循环：

while (child > 0)

当child大于0时，继续执行循环。循环的目的是将child节点与其父节点进行比较，并根据需要进行交换。

4. 比较child节点与其父节点的大小：

if (a[child] < a[parent])

如果child节点的值小于其父节点的值，说明需要进行交换。这是一个小堆的向上调整操作。如果想要实现大堆的向上调整，需要将判断条件改为>。

5. 交换节点值和更新索引：

Swap(&a[child], &a[parent]);
child = parent;
parent = (child - 1) / 2;

交换child节点和父节点的值，然后更新child和parent的值，使其指向交换后的节点。

6. 循环结束：

else
{
    break;
}

如果child节点大于等于其父节点，说明调整完成，跳出循环。

通过这个向上调整的操作，可以将新插入的元素调整到合适的位置，以保证堆的性质。

---

向下调整算法

如果堆中某个节点的值被修改，如何调整这个堆的结构保证其依然满足堆的要求？

当堆中的某个节点的值发生改变时（例如，该节点的值被修改），需要进行向下调整操作来保持堆的性质。

向下调整的基本思想是将当前节点与其子节点进行比较，并根据堆的类型（大堆或小堆）选择合适的交换操作。如果当前节点的值小于（或大于）其子节点的值，那么需要将当前节点与其子节点中的较大（或较小）值进行交换。然后，继续向下调整交换后的子节点，直到满足堆的性质为止。

示意图如下：
在顺序表中的效果（实际效果）：

代码如下：

//向下调整
void AdjustDown(HPDataType* a, int size, int parent)
{
	int child = parent * 2 + 1;

	while (child < size)
	{
		if (child + 1 < size && a[child + 1] > a[child])
		{
			child++;
		}

		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

函数AdjustDown的参数包括一个整型数组a，数组大小size，以及一个表示待调整节点的下标parent。

首先，计算待调整节点的左子节点下标child = parent * 2 + 1。

然后，进入一个循环，判断child是否越界。如果child < size，则说明待调整节点有左子节点。

在循环中，首先判断是否存在右子节点，并且右子节点的值大于左子节点的值，如果满足这个条件，则将child更新为右子节点的下标。

接下来，判断child节点的值是否大于parent节点的值。如果满足这个条件，则交换child和parent节点的值，并更新parent为child，再次计算child的值。

如果child节点的值不大于parent节点的值，则退出循环。

函数结束后，即可保证以parent节点为根的子树满足堆的性质。

---

堆的插入

为了不破坏堆的结构，我们一般会在堆的末尾插入节点，当插入完节点后，还要将这个节点放到合适的为止，那么此时就需要使用到向上调整算法将此节点调整到合适的位置。

比如这样：

但是由于我们的堆结构是基于顺序表实现的，在插入最后一个元素时，还要考虑是否空间充足，从而判断是否需要扩容。

代码如下：

//插入
void HeapPush(HP* php, HPDataType x)
{
	assert(php);
	if (php->size == php->capacity)
	{
		int newCapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
		HPDataType* tmp = (HPDataType*)realloc(php->a, newCapacity * sizeof(HPDataType));
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(-1);
		}
		php->a = tmp;
		php->capacity = newCapacity;
	}

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

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

具体解释如下：

1. 首先，使用assert宏确保传入的二叉堆指针php不为空。

---

2. 如果二叉堆已满（即php->size等于php->capacity），则需要扩容。这里使用了realloc函数重新分配内存空间，新的容量为原容量的两倍。如果realloc失败，则打印错误信息并退出程序。分配成功后，将新的空间地址保存在tmp指针中。

---

3. 将tmp指针赋值给php->a，即将php->a指向新的内存空间。

---

4. 将新插入的元素x赋值给php->a的最后一个位置，即php->a[php->size]。然后，将php->size加1，表示堆的大小增加。

---

5. 调用AdjustUp函数，对刚插入的元素进行向上调整（上浮操作），以保持二叉堆的性质。具体来说，就是将x与其父节点比较并交换，直到x不再比其父节点小或者已经到达堆顶位置。

---

堆的删除

堆的删除要求必须删除堆顶，这样做的意义是每次都可以取出堆的最大值或最小值。
要注意，当堆顶是最大值时，最后一个节点不一定是最小值（对于大堆）。

比如这个堆结构中，最大值是第一个节点，而最小值不是最后一个节点。

那么如何直接删掉最顶上的节点呢？删掉节点后又要如何保证这个堆符合要求呢？
对于这个问题，我们采取的方法是：

将第一个节点与最后一个节点交换
然后删除尾部节点（即被交换前的第一个节点）
将堆顶节点（即交换前的最后一个节点）向下调整

示意图如下：

代码实现：

//删除
void HeapPop(HP* php)
{
	assert(php);
	assert(php->size > 0);

	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;//删除尾节点

	AdjustDown(php->a, php->size, 0);
}

以下是对代码的详细解释：

1. 首先，代码使用断言来确保传入的堆指针 php 不为空，并且堆的大小 php->size 大于 0。

---

2. 接下来，代码调用 Swap 函数来交换根节点 php->a[0] 和最后一个节点 php->a[php->size - 1] 的值。这样就将堆顶的元素移动到最后。

---

3. 然后，代码将堆的大小减一，表示删除了一个节点。

---

4. 最后，代码调用 AdjustDown 函数将交换后的根节点下沉到合适的位置，以保持堆的特性。

通过这些步骤，HeapPop 函数完成了从堆中删除根节点的操作，并且保持了堆的特性。

---

得到堆顶元素

想要得到堆顶的元素，其实就是拿到a[0]。

//返回堆顶
HPDataType HeapTop(HP* php)
{
	assert(php);
	assert(php->size > 0);

	return php->a[0];
}

过于简单，不做解释了。

---

判断堆是否为空

判断堆是否为空，即判断size是不是0。
代码如下：

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

	return php->size == 0;
}

---

堆的应用

有了以上接口，我们现在就利用堆来实现一些具体功能：

TopK问题

所谓TopK问题，就是在一串数据中，找到最大的K个数字。
那么我们要如何实现这样功能呢？
不少人会想到，将整个数组转化为一个大堆，然后取出堆中最前面的k个节点值，这个方法很好想，但是建堆的复杂度可不低，而且将一个数组转化为一个堆，那为什么不直接对这个数组排序？

不妨想想，我们的目的只是取出最大的k个数字，我们可以用一块空间来存储最大的k个数字。接着遍历这个数组，将目前最大的K个数字存在这个空间中，最后我们只需要遍历一次数组，就可以取出最大的K个数字了。

对于这个用于存储最大的K个数据的空间，我们要保证每次都拿出最大的K个数据中最小的1个节点去和后续的值比较，只要一个数据可以比之前数据的最大的K个数据中最小的那个数字大，那么它就可以进入当前的TopK。

那么我们要如何维护这样的一个空间，保证每次都可以取出最小的那个值呢？
答案是建一个小堆，为什么是小堆？
因为小堆的堆顶就是这个堆中最小的数字，在对比后续数值时，将其与当前的堆顶对比即可。

整体思路如下：

• 取出数据的前K个数值，创建一个K个数的小堆
• 遍历剩余数据，将每个数据与堆顶比较，如果比堆顶大，就替换掉堆顶
• 当堆顶被替换后，为了保证堆的结构，对堆顶向下调整到合适位置。

建堆
那么要如何创建一个K个数字的小堆？
假设我们已经创建了一个可以放K个数据的数组minheap[]以及被查找的数组a[]。

我们只需要每次都把数据放到minheap[]的末尾，然后将尾部向上调整到指定位置即可：

	for (int i = 0; i < k; i++)
	{
		minheap[i] = a[i];
		AdjustUp(minheap, i);
	}

图示如下：

这个过程中，我们建立了一个有11个元素的堆，每次插入一个值，都将其向上调整到合适的位置。

将后续数值与节点的最小值比较
我们先前已经把数组a[]中的前K个数据取出来了，接下来就要将剩下的size-k个数据一一与堆顶比较。一旦其比当前的堆顶大，就将其向下调整到指定位置，保证堆顶依然是目前的TopK的最小值。

代码如下：

	for (int i = k; i < size; i++)
	{
		if (a[i] > minheap[0])
		{
			minheap[0] = a[i];
			AdjustDown(minheap, k, 0);
		}
	}

总代码如下：

void PrintTopK(int* a, int size, int k)
{
	//------------------------------
	//建立一个k个数字的小堆
	int* minheap = (int*)malloc(sizeof(int) * k);
	if (minheap == NULL)
	{
		perror("malloc fail");
		return;
	}

	for (int i = 0; i < k; i++)
	{
		minheap[i] = a[i];
		AdjustUp(minheap, i);
	}

	//-------------------------------
	//将后续数字与当前的堆中数据比较
	for (int i = k; i < size; i++)
	{
		if (a[i] > minheap[0])
		{
			minheap[0] = a[i];
			AdjustDown(minheap, k, 0);
		}
	}

	for (int i = 0; i < k; i++)
	{
		printf("%d ", minheap[i]);
	}
	printf("\n");
}

通过这样的一个算法，我们可以只遍历一次数组，就可以将数组中的最大的K个值取出来。

---