堆
堆的定义
定义：
堆是一种数据结构，本质上是一个特殊的树结构，它是一个完全二叉树，其中每个节点的值都大于等于其子节点的值（对于大堆）或者小于等于其子节点的值（对于小堆）。
根据以上定义，一个数据结构可以称为堆有两个条件：
- 是一颗完全二叉树
- 每个父节点的值大于其子节点的值 或 每个父节点的值大于其子节点的值
其中，每个父节点的值大于其子节点的值称为大堆，每个父节点的值小于其子节点的值称为小堆。
以下就是一个大堆：
由于堆具有一定的规律，所以比一般的二叉树更有实际意义，比如堆排序以及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; } } }
代码详解：
- 函数定义：
void AdjustUp(HPDataType* a, int child)
该函数接受两个参数：指向数组的指针a和待调整元素的索引child。HPDataType是堆中存储的元素类型。
- 定义父节点索引：
int parent = (child - 1) / 2;
根据完全二叉树的性质，节点i的父节点索引是(i - 1) / 2，所以计算出child节点的父节点索引。
- 进入循环：
while (child > 0)
当child大于0时，继续执行循环。循环的目的是将child节点与其父节点进行比较，并根据需要进行交换。
- 比较
child节点与其父节点的大小：
if (a[child] < a[parent])
如果child节点的值小于其父节点的值，说明需要进行交换。这是一个小堆的向上调整操作。如果想要实现大堆的向上调整，需要将判断条件改为>。
- 交换节点值和更新索引：
Swap(&a[child], &a[parent]); child = parent; parent = (child - 1) / 2;
交换child节点和父节点的值，然后更新child和parent的值，使其指向交换后的节点。
- 循环结束：
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); }
具体解释如下：
- 首先，使用
assert宏确保传入的二叉堆指针php不为空。
- 如果二叉堆已满（即
php->size等于php->capacity），则需要扩容。这里使用了realloc函数重新分配内存空间，新的容量为原容量的两倍。如果realloc失败，则打印错误信息并退出程序。分配成功后，将新的空间地址保存在tmp指针中。
- 将
tmp指针赋值给php->a，即将php->a指向新的内存空间。
- 将新插入的元素
x赋值给php->a的最后一个位置，即php->a[php->size]。然后，将php->size加1，表示堆的大小增加。
- 调用
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); }
以下是对代码的详细解释：
- 首先，代码使用断言来确保传入的堆指针
php不为空，并且堆的大小php->size大于 0。
- 接下来，代码调用
Swap函数来交换根节点php->a[0]和最后一个节点php->a[php->size - 1]的值。这样就将堆顶的元素移动到最后。
- 然后，代码将堆的大小减一，表示删除了一个节点。
- 最后，代码调用
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个值取出来。
