堆的概念实现

前言

本文将详细讲解堆。堆是一种二叉树（一般是完全二叉树）使用顺序结构的数组来存储。
tip：这里我们需要注意区分堆在不同地方的含义，这里的堆是一个数据结构，操作系统虚拟进程地址空间的堆是操作系统中管理内存的一块区域分段。

一、堆的概念及结构

1、堆的概念

如果有一个关键码的集合K，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足堆中某个节点的值总是不大于（或不小于）其父节点的值，则称为大堆（小堆）。

将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

tip：

• 堆总是一颗完全二叉树。
• 大堆：树中所有父亲都大于或等于孩子。
• 小堆：树中所有父亲都小于或等于孩子。
• 注意：堆不一定是有序的，因为左右孩子谁大谁小并没有限制。

2、堆的结构

tip：学习堆我们一定要画图，因为堆在内存中的存储结构是一个数组，但元素之间的逻辑是一颗二叉树，我们很难可以将其想象出来，所以学堆画图很重要！

二、堆的实现

虽然堆分为两类，大根堆和小根堆，但是他们的结构与功能都是类似的，所以这里我们实现一个大堆为例就可以了。

我们先预览堆的结构与所需的接口函数：

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>//堆——完全二叉树
//虽然堆在内存上是用一段物理地址连续的存储单元依次存储的，但是逻辑关系上是一颗完全二叉树
//堆又分为大根堆和小根堆
//大根堆：树中所有父亲都大于或等于孩子
//小根堆：树中所有父亲都小于或等于孩子
//大根堆和小根堆的实现基本相似，所以这里我们以实现一个大根堆为例typedef int HPDataType;//重命名堆中数据的类型——》优点：①一改全改；②见名知意
typedef struct Heap
{HPDataType* arr;//指向堆区申请的数组int size;//存储有效数据个数int capacity;//堆的容量空间
}HP;//堆的初始化——初始化堆的成员变量
void HeapInit(HP* php);//堆的销毁——动态申请的空间，自己要记得销毁，否则可能造成内存泄漏
void HeapDestroy(HP* php);//交换
void Swap(HPDataType* e1, HPDataType* e2);//堆的向上调整
void AdjustUp(HPDataType* arr, int child);//堆的插入
void HeapPush(HP* php, HPDataType x);//打印堆数组
void HeapPrint(HP* php);//判断堆是否为空
bool HeapIsEmpty(HP* php);//堆的向下调整
void AdjustDown(HPDataType* arr, int n, int parent);//堆的删除
void HeapPop(HP* php);//获取堆顶元素
HPDataType HeapTop(HP* php);//获取堆的有效元素个数
int HeapSize(HP* php);

1、堆的结构

堆由三个成员变量组成，分别是arr指针指向动态申请的数组、size存储堆的有效数据个数、capacity存储堆的容量，所以堆是一个复杂结构，我们将其定义为结构体。

typedef int HPDataType;//重命名堆中数据的类型——》优点：①一改全改；②见名知意
typedef struct Heap
{HPDataType* arr;//指向堆区申请的数组int size;//存储有效数据个数int capacity;//堆的容量空间
}HP;

tip：

• 建议将堆中存储的数据的类型typedef，typedef 一可以方便我们更改堆的类型，二见名知意。

2、堆的初始化

堆的初始化模块功能：初始化堆对象的三个成员变量

//堆的初始化——初始化堆的成员变量
void HeapInit(HP* php)
{//断言指针的有效性，php不可能为空assert(php);//初始化堆的成员php->arr = (HPDataType*)malloc(sizeof(HPDataType) * 4);if (NULL == php->arr){//扩容失败perror("HeapInit::malloc");return;}php->size = 0;php->capacity = 4;
}

3、堆的销毁

堆的销毁模块功能：清理堆对象使用的资源，并销毁堆对象中动态申请的资源。

//堆的销毁——动态申请的空间，自己要记得销毁，否则可能造成内存泄漏
void HeapDestroy(HP* php)
{assert(php);//释放堆对象申请的动态空间free(php->arr);//free之后php->arr仍指向原来的空间，可能造成非法访问或多次释放，建议置为空php->arr = NULL;php->size = 0;php->capacity = 0;
}

4、堆的插入(重点)

堆的插入模块功能：先在数组尾插入数据，数据再向上调整找到自己在大堆中的位置。

问题1： 堆插入为什么只有一种？

因为堆要满足大根堆或小根堆的性质，头插和任意位置插入会改变堆原本的结构，而尾插不会改变堆原本的结构。

问题2： 已知有一个数组，它是按照大根堆的性质存储的。现在我们在数组尾插入一个数据80，仍想让数组按照大根堆存储，该怎么实现？

1. 使用向上调整算法实现。
2. 向上调整算法的思想：
   • 将目标节点（孩子结点）与其父节点比较。
   • 如果目标节点大于其父节点，交换两个节点的值，并继续向上比较。
   • 结束向上比较的条件：①如果目标节点小于其父节点，则停止向上比较；②最坏的情况是向上比较到根才结束。
3. 因为其过程是不断的向上比较，所以将其叫做向上调整算法。
   
   tip：向上调整的前提是除了目标位置，前面数据构成大堆/小堆。

（1）交换两个数据

因为在堆中许多地方都会交换两个数据，所以我们将其模块化。

//交换——有多个模块需要交换，所以将其模块化
void Swap(HPDataType* e1, HPDataType* e2)
{HPDataType temp = *e1;*e1 = *e2;*e2 = temp;
}

tip：

• 注意：值传递不会改变形参的改变不会改变实参。

（2）向上调整

注意：向上调整的前提是除了目标位置，前面数据构成大堆/小堆。

//堆的向上调整
void AdjustUp(HPDataType* arr, int child)
{//存储父亲的下标int parent = (child - 1) / 2;//大堆向上调整：当孩子大于父亲时，孩子与父亲交换//向上调整的结束条件：//①最坏情况：向上到根才结束，即child = 0(parent<0)。但注意不能用parent < 0作为结束，因为parent = (child - 1) / 2不可能小于0.//②特殊情况：当孩子不大于父亲时结束。while (child > 0){if (arr[child] > arr[parent]){//交换Swap(&arr[child], &arr[parent]);//继续向上调整child = parent;parent = (child - 1) / 2;}else{//跳出循环break;}}
}

tip：

• 最坏情况是到根结束，注意不能用parent < 0来判断，因为parent = （child - 1）/ 2不可能小于0。
• 小根堆的向上调整与大根堆类似，只需将if中的arr[child] > arr[parent]改成arr[child] < arr[parent]即可。

（3）堆的插入

//堆的插入
void HeapPush(HP* php, HPDataType x)
{assert(php);//1、向堆插入数据，要先判断是否扩容if (php->size == php->capacity){//扩容//realloc可能扩容失败，所以先使用一个临时变量保存realloc的返回值HPDataType* temp = (HPDataType*)realloc(php->arr, sizeof(HPDataType) * php->capacity * 2);//判断是否扩容成功if (temp != NULL){//扩容成功，仍然使用php->arr指向申请的空间，并将temp置为空php->arr = temp;temp = NULL;//注意别忘记更新容量php->capacity *= 2;}else{perror("realloc");return;}}//2、堆的插入——先在数组尾插入数据，再向上调整//①数组尾插——不需要挪动，时间复杂度O(1)php->arr[php->size] = x;php->size++;//②向上调整AdjustUp(php->arr, php->size - 1);
}

tip：

• 注意我们插入数据之前，要检查是否需要扩容。

5、堆的判空

堆的判空模块功能：如果堆为空，则返回真；反之，返回假。

//判断堆是否为空
bool HeapIsEmpty(HP* php)
{assert(php);//当堆中有效个数为0时，堆为空return 0 == php->size;
}

tip：

• 判断一个变量与一个常量是否相等时，建议变量做右操作数，提高代码的健壮性。

6、堆的删除(重点)

堆的删除模块功能：删除堆顶的元素。

问题1： 堆的删除为什么只能删除堆顶元素？

因为堆的性质，堆顶元素的值最大或最小。

所以删除堆顶元素才有意义，删除掉最大的之后我们可以继续选出第二大的。

问题2： 我们直接删除堆顶？

我们不会直接删除堆顶元素，因为直接删除堆顶元素有两大问题：

• 数组头删，需要挪动数据，时间复杂度为O(N)，效率低。
• 父子兄弟关系全乱了。

问题3： 怎样删除堆顶？

思路：

1. 交换：把堆顶元素与最后一个元素交换
2. 删除堆顶：数组尾删，直接size–即可
3. 向下调整：运用向下调整算法，确保堆的结构。

问题4： 怎样向下调整？

思路：

1. 通过假设法选出左右孩子较大的那个孩子结点
2. 将较大的那个孩子结点与父节点比较，如果比父节点大，则交换
3. 继续向下比较，直到比父节点小才停止，最坏的情况是，向下比较到叶子才停止。
   
   tip：向下调整的前提是左右子树都是大堆/小堆。

（1）向下调整

注意：向下调整的前提是左右子树都是大堆/小堆。

//堆的向下调整
void AdjustDown(HPDataType* arr, int n, int parent)
{//假设法：定义一个变量存储较大孩子的下标，先假设左孩子大，再通过if确定假设是否成立。int child = parent * 2 + 1;//大堆向下调整：当父亲小于较大的孩子，孩子与父亲交换//向下结束的条件：//①最坏情况： 向下到叶子结束，即child(parent * 2 + 1) > n。//②特殊情况：当孩子不小于父亲时结束。while (child < n){//if确定假设是否成立//注意：要先判断child + 1是否为堆有效数据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;}}
}

tip：

• 比较左右孩子的时候，需要先判断右孩子是否为堆的有效数据，当child(parent * 2 + 1) > n，没有右孩子。
• 小根堆的向下调整与大根堆类似，只需将if中的arr[child] > arr[parent]改成arr[child] < arr[parent]即可。

（2）堆的删除

//堆的删除
void HeapPop(HP* php)
{assert(php);//删除堆不能为空assert(!HeapIsEmpty(php));//堆只有删除堆顶元素才有意义//问题：是直接删吗？//答案是：不是，直接删，有两个问题——①效率低，挪动数据时间复杂度O(N)；②堆的父子兄弟关系全乱了//①交换堆顶与堆尾Swap(&php->arr[0], &php->arr[php->size - 1]);//②数组尾删php->size--;//③向下调整AdjustDown(php->arr, php->size, 0);
}

tip：

• 在删除数据之前，需要判断堆是否为空。
• 堆删除的思路口诀：一交换二删除三向下调整。

7、获取堆顶元素

//获取堆顶元素
HPDataType HeapTop(HP* php)
{assert(php);//断言堆不为空assert(!HeapIsEmpty(php));return php->arr[0];
}

tip：

• 为了程序的健壮性，在获取之前断言堆不为空。
• 获取堆顶元素，直接返回数组下标为0的元素即可

8、获取堆的有效数据个数

//获取堆的有效元素个数
int HeapSize(HP* php)
{assert(php);return php->size;
}

tip：

• 直接返回size即可。

9、堆的打印

//打印堆数组
void HeapPrint(HP* php)
{assert(php);int i = 0;for (i = 0; i < php->size; ++i){printf("%d ", php->arr[i]);}printf("\n");
}

tip：

• 堆在内存中是连续存储的其本质就是数组，所以使用for循环就打印了。

三、总代码

1、接口声明模块

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>//堆——完全二叉树
//虽然堆在内存上是用一段物理地址连续的存储单元依次存储的，但是逻辑关系上是一颗完全二叉树
//堆又分为大根堆和小根堆
//大根堆：树中所有父亲都大于或等于孩子
//小根堆：树中所有父亲都小于或等于孩子
//大根堆和小根堆的实现基本相似，所以这里我们以实现一个大根堆为例typedef int HPDataType;//重命名堆中数据的类型——》优点：①一改全改；②见名知意
typedef struct Heap
{HPDataType* arr;//指向堆区申请的数组int size;//存储有效数据个数int capacity;//堆的容量空间
}HP;//堆的初始化——初始化堆的成员变量
void HeapInit(HP* php);//堆的销毁——动态申请的空间，自己要记得销毁，否则可能造成内存泄漏
void HeapDestroy(HP* php);//交换
void Swap(HPDataType* e1, HPDataType* e2);//堆的向上调整
void AdjustUp(HPDataType* arr, int child);//堆的插入
void HeapPush(HP* php, HPDataType x);//打印堆数组
void HeapPrint(HP* php);//判断堆是否为空
bool HeapIsEmpty(HP* php);//堆的向下调整
void AdjustDown(HPDataType* arr, int n, int parent);//堆的删除
void HeapPop(HP* php);//获取堆顶元素
HPDataType HeapTop(HP* php);//获取堆的有效元素个数
int HeapSize(HP* php);

2、接口实现模块

#include"Heap.h"//堆的初始化——初始化堆的成员变量
void HeapInit(HP* php)
{//断言指针的有效性，php不可能为空assert(php);//初始化堆的成员php->arr = (HPDataType*)malloc(sizeof(HPDataType) * 4);if (NULL == php->arr){//扩容失败perror("HeapInit::malloc");return;}php->size = 0;php->capacity = 4;
}//堆的销毁——动态申请的空间，自己要记得销毁，否则可能造成内存泄漏
void HeapDestroy(HP* php)
{assert(php);//释放堆对象申请的动态空间free(php->arr);//free之后php->arr仍指向原来的空间，可能造成非法访问或多次释放，建议置为空php->arr = NULL;php->size = 0;php->capacity = 0;
}//交换——有多个模块需要交换，所以将其模块化
void Swap(HPDataType* e1, HPDataType* e2)
{HPDataType temp = *e1;*e1 = *e2;*e2 = temp;
}//堆的向上调整
void AdjustUp(HPDataType* arr, int child)
{//存储父亲的下标int parent = (child - 1) / 2;//大堆向上调整：当孩子大于父亲时，孩子与父亲交换//向上调整的结束条件：//①最坏情况：向上到根才结束，即child = 0(parent<0)。但注意不能用parent < 0作为结束，因为parent = (child - 1) / 2不可能小于0.//②特殊情况：当孩子不大于父亲时结束。while (child > 0){if (arr[child] > arr[parent]){//交换Swap(&arr[child], &arr[parent]);//继续向上调整child = parent;parent = (child - 1) / 2;}else{//跳出循环break;}}
}//堆的插入
void HeapPush(HP* php, HPDataType x)
{assert(php);//1、向堆插入数据，要先判断是否扩容if (php->size == php->capacity){//扩容//realloc可能扩容失败，所以先使用一个临时变量保存realloc的返回值HPDataType* temp = (HPDataType*)realloc(php->arr, sizeof(HPDataType) * php->capacity * 2);//判断是否扩容成功if (temp != NULL){//扩容成功，仍然使用php->arr指向申请的空间，并将temp置为空php->arr = temp;temp = NULL;//注意别忘记更新容量php->capacity *= 2;}else{perror("realloc");return;}}//2、堆的插入——先在数组尾插入数据，再向上调整//①数组尾插——不需要挪动，时间复杂度O(1)php->arr[php->size] = x;php->size++;//②向上调整AdjustUp(php->arr, php->size - 1);
}//打印堆数组
void HeapPrint(HP* php)
{assert(php);int i = 0;for (i = 0; i < php->size; ++i){printf("%d ", php->arr[i]);}printf("\n");
}//判断堆是否为空
bool HeapIsEmpty(HP* php)
{assert(php);//当堆中有效个数为0时，堆为空return 0 == php->size;
}//堆的向下调整
void AdjustDown(HPDataType* arr, int n, int parent)
{//假设法：定义一个变量存储较大孩子的下标，先假设左孩子大，再通过if确定假设是否成立。int child = parent * 2 + 1;//大堆向下调整：当父亲小于较大的孩子，孩子与父亲交换//向下结束的条件：//①最坏情况： 向下到叶子结束，即child(parent * 2 + 1) > n。//②特殊情况：当孩子不小于父亲时结束。while (child < n){//if确定假设是否成立//注意：要先判断child + 1是否为堆有效数据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 HeapPop(HP* php)
{assert(php);//删除堆不能为空assert(!HeapIsEmpty(php));//堆只有删除堆顶元素才有意义//问题：是直接删吗？//答案是：不是，直接删，有两个问题——①效率低，挪动数据时间复杂度O(N)；②堆的父子兄弟关系全乱了//①交换堆顶与堆尾Swap(&php->arr[0], &php->arr[php->size - 1]);//②数组尾删php->size--;//③向下调整AdjustDown(php->arr, php->size, 0);
}//获取堆顶元素
HPDataType HeapTop(HP* php)
{assert(php);//断言堆不为空assert(!HeapIsEmpty(php));return php->arr[0];
}//获取堆的有效元素个数
int HeapSize(HP* php)
{assert(php);return php->size;
}

3、功能测试模块

#include"Heap.h"int main()
{//定义堆变量HP hp;//初始化HeapInit(&hp);//插入数据HeapPush(&hp, 6);HeapPush(&hp, 16);HeapPush(&hp, 36);HeapPush(&hp, 56);HeapPush(&hp, -1);HeapPush(&hp, 5);HeapPush(&hp, -16);HeapPush(&hp, 35);HeapPush(&hp, 19);HeapPush(&hp, 9);HeapPush(&hp, 6);HeapPush(&hp, 18);HeapPrint(&hp);//找出前k个大的数int k = 0;scanf("%d", &k);while (!HeapIsEmpty(&hp) && k--){printf("%d ", HeapTop(&hp));//删除HeapPop(&hp);}printf("\n");HeapDestroy(&hp);return 0;
}

运行结果：