前言 往期我们的学习中讲到了二叉树
它可以帮我们解决很多问题，而类似的数据结构还有很多
今天，我们就来聊聊——堆
一、堆是什么？1. 堆的定义 堆：
上期我们讲讲到了二叉树，知道了完全二叉树以及非完全二叉树
而堆，就是一个完全二叉树，但在其基础上增加了一些东西，变得更加有序
2. 堆的分类堆从排序的角度，被分为两类，一个是大堆，一个是小堆
大堆 在大堆中，任何一个父结点的值都要大于或等于子结点的值
（只是父亲与孩子之间的比较，与兄弟结点无关—）
如图，这就是一个大堆：
小堆 而在小堆中恰恰相反，任何一个子结点的值都要大于或等于父结点的值
（只是父亲与孩子之间的比较，与兄弟结点无关—）
如图，这就是一个小堆：
在这里插入图片描述3. 堆的特点由于在大堆中，任何一个父结点的值都要大于或等于子结点的值
在小堆中，任何一个子结点的值都要大于或等于父结点的值
故堆有一个很重要的特点：
在堆中，根结点的值最大或最小，故可通过堆来找极大值和极小值
二、堆的实现（小堆）（本文实现的堆是小堆，但原理一样）
1. 用什么来实现？想要实现堆，首先要想清楚要用什么实现堆
之前，我们讲了完全二叉树的存储，提到完全二叉树的编号是连续的，对于完全二叉树来说，我们可以用数组来进行存储，用下标来进行编号
而堆，就是一个完全二叉树，所以直接使用数组实现即可
综上所诉，使用数组的结构来实现堆更优
2. 实现思路这里可以拿顺序表来做参考，往期我们详解了顺序表的实现，大家感兴趣的可以去看看
链接：【C语言】数据结构——顺序表超详解!!!（包含顺序表的实现)
与顺序表同理，堆的实现也应该有三名成员：
1. 指向一个数组的指针
2. 堆内的总元素
3. 堆内的总容量
3. 代码实现本文以创建一个 int 类型的堆为例
（1）创建头文件&源文件 之前在讲解扫雷游戏中我就提到:
在写复杂程序时要养成写多个头文件&源文件的好习惯，这样条理就很清晰也不会乱
详见【C语言】扫雷游戏详解（包含递归，变色，记录时间等）
在这里插入图片描述如图:
创建了一个 “ Heap.h "头文件
用于存放用来放函数的声明和一些库函数的头文件
创建了一个 “ Heap.c "源文件
用于用来放函数的定义(堆的主体)
还有一个 ” Test.c "源文件
用于测试实现的堆的运行效果
（2）定义堆（定义） 首先我们要定义一个堆
代码演示：（内有注释）
（在头文件“ Heap.h "中写）
代码语言：javascript复制//重定义，方便修改类型
typedef int HPDataType;
//定义堆
typedef struct Heap
{
HPDataType* a; //数组指针
int size; //总元素
int capacity; //容量
}Heap; 在定义堆的代码中，有两个需要注意的点：
本文是以 int 类型为例，但如果以后要将堆的类型修改成 char 类型或是其他类型一个一个修改就很麻烦
所以我们重定义int类型为HPDataType,并将接下来代码中的int类型全部写成HPDataType
这是为了方便我们以后对类型进行修改，仅需将int 改为其他类型即可在定义堆的同时重定义堆变量名为Heap方便以后使用（3）堆的初始化（初始化） 定义完堆后，肯定要对堆进行初始化，内容全部置 0 / NULL
代码演示：（内有注释）
（其中 hp 是一个堆指针类型的指针，下同）
在“ Heap.h "头文件中写到：
代码语言：javascript复制// 堆的初始化
void HeapInit(Heap* hp);在“ Heap.c "源文件中写到：
代码语言：javascript复制// 堆的初始化
void HeapInit(Heap* hp)
{
assert(hp);
//断言空指针
hp->a = NULL;
hp->capacity = 0;
hp->size = 0;
//全部初始化置 0 / NULL
} 在写堆的实现的代码中，有一个很重要的点：
当我们函数在进行传参时，可能会传入空指针，而我们知道空指针是不能进行解引用的
故为了我们的代码更加健壮，可以加入assert 断言来判断是否符合条件，在之后的代码中也都有
关于更加详细的assert 断言介绍可参见下文：
【C语言】带你层层深入指针——指针详解3（野指针、assert等）
（4）堆的销毁（销毁） 在我们的程序运行完毕后，当然要对堆进行销毁，以免占用内存
代码演示：（内有注释）
（其中 hp 是一个堆指针类型的指针，下同）
在“ Heap.h "头文件中写到：
代码语言：javascript复制// 堆的销毁
void HeapDestory(Heap* hp);在“ Heap.c "源文件中写到：
代码语言：javascript复制// 堆的初始化
void HeapInit(Heap* hp)
{
assert(hp);
//断言空指针
hp->a = NULL;
hp->capacity = 0;
hp->size = 0;
//全部初始化置 0 / NULL
}
// 堆的销毁
void HeapDestory(Heap* hp)
{
assert(hp);
//断言空指针
free(hp->a);
//释放内存
hp->a = NULL;
hp->capacity = 0;
hp->size = 0;
//全部初始化置 0 / NULL
}（5）插入数据（入堆）第一步：怎么插入？ 在入堆时，由于堆的本质是数组，故从头或中间插入很不方便，还要挪动数据，故我们选择尾插数据入堆
第二步：空间不够时咋办？ 堆的空间是动态管理的，故当堆的空间不足时，可再开辟一些空间使用（动态增容）
但是存在一个问题：
我们到底要开辟多大的空间来使用呢？
1. 若一次性开辟的空间过大，可能会造成空间的浪费
2. 若一次性开辟的空间过小，就可能会导频繁的开辟空间，这样运行的效率就会大大降低
经过科学研究，发现每次增容 2 倍 & 3 倍 空间最为合适
当原空间为 100 的空间不足时，就增容到 200 空间
（本文选择的是每次增容 2 倍 ）
第三步：调整堆 在插入之后，该堆就不一定还是小堆了，故需要做出调整，将尾插的数据向上调整
那么该怎么调整呢？
由于我们建的是小堆，所以若孩子小于父亲，孩子就要向上调整，将父亲与孩子的值对调
直到父亲小于孩子，调整结束
代码演示：（内有注释）
（其中 hp 是一个堆指针类型的指针，下同）
在“ Heap.h "头文件中写到：
代码语言：javascript复制// 堆的插入
void HeapPush(Heap* hp, HPDataType x);在“ Heap.c "源文件中写到：
（插入函数）
代码语言：javascript复制// 堆的插入（尾插+调整）
void HeapPush(Heap* hp, HPDataType x)
{
assert(hp);
//断言空指针
if (hp->size == hp->capacity)
//当size=capacity时就表示空间不足，此时需要增容，故进入if语句
{
//先设置新变量，增容后再赋值
int newcapacity = hp->capacity == 0 ? 4 : 2 * hp->capacity;
//设置一个三目操作符判断原空间是否为 0
//当原空间为0时给空间开辟 4 字节；当原空间不为0时给空间增容 2倍
HPDataType* tmp = (HPDataType*)realloc(hp->a, newcapacity * sizeof(HPDataType));
//由于是在原空间的基础上给空间增容，故我们这里使用 realloc函数 增容
//增容大小为上面的 newcapacity *（类型大小）
if (tmp == NULL)
//加一个 if语句 防止增容失败
{
perror("realloc fail");
return;
}
//没有问题后就赋值
hp->a = tmp;
hp->capacity = newcapacity;
}
hp->a[hp->size] = x;
hp->size++;
//插入完后就向上调整
AdJustUp(hp->a, hp->size - 1);
}（向上调整函数）
代码语言：javascript复制// 将尾插的元素向上调整
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;
}
}
}（交换函数）
代码语言：javascript复制// 交换两个数的值
void Swap(HPDataType* x, HPDataType* y)
{
HPDataType tmp = *x;
*x = *y;
*y = tmp;
}（6）删除数据（出堆） 对于堆来说，要删除数据一般都是删除堆顶的元素
但是删除后想要调整回一个小堆就不容易了
所以我们采用一种间接删除的方式
方法：
先将堆顶和堆尾的值交换，然后删除堆尾数据
此时相当于把之前的堆顶数据删除了
而且对于数组来说尾删是很简单的，只需要将总个数减一就行然后就开始处理首元素了，和尾插同理，需要调整，但这里是向下调整
由于我们建的是小堆，所以若父亲大于孩子，父亲就要向下调整，将父亲与孩子的值对调
直到父亲小于孩子，调整结束代码演示：（内有注释）
（其中 hp 是一个堆指针类型的指针，下同）
在“ Heap.h "头文件中写到：
代码语言：javascript复制// 堆的删除
void HeapPop(Heap* hp);在“ Heap.c "源文件中写到：
（删除函数）
代码语言：javascript复制// 堆的删除（交换+头删+调整）
void HeapPop(Heap* hp)
{
assert(hp);
assert(hp->size > 0);
//断言空指针
//断言顺序表不能为空
Swap(&(hp->a[0]), &(hp->a[hp->size - 1]));
hp->size--;
//先将头部和尾部的值交换
//并且size--（类似删除尾部）
AdJustDown(hp->a, 0, hp->size);
//将头部的数据向下调整
}（向下调整函数）
代码语言：javascript复制// 将交换的元素向下调整
void AdJustDown(HPDataType* a, int parent, int size)
{
// 先假设左孩子小
int child = 2 * parent + 1;
while (child <= size - 1)
{
if (child + 1 <= size - 1 && a[child + 1] < a[child])
{
child++;
}
if (a[child] < a[parent])//若父亲大于孩子，父亲就要向下调整
{
Swap(&a[child], &a[parent]);
parent = child;
child = 2 * parent + 1;
}
else
{
break;
}
}
}（交换函数）
代码语言：javascript复制// 交换两个数的值
void Swap(HPDataType* x, HPDataType* y)
{
HPDataType tmp = *x;
*x = *y;
*y = tmp;
}（7）获取堆顶元素 这个很简单，直接用下标进行访问数据
再返回所对应的值
代码演示：（内有注释）
（其中 hp 是一个堆指针类型的指针，下同）
在“ Heap.h "头文件中写到：
代码语言：javascript复制// 取堆顶的数据
HPDataType HeapTop(Heap* hp);在“ Heap.c "源文件中写到：
代码语言：javascript复制// 取堆顶的数据
HPDataType HeapTop(Heap* hp)
{
assert(hp);
assert(hp->size > 0);
//断言空指针
//断言顺序表不能为空
return hp->a[0];
}（8）获取堆的数据个数 这个很简单
直接返回所对应的值
代码演示：（内有注释）
（其中 hp 是一个堆指针类型的指针，下同）
在“ Heap.h "头文件中写到：
代码语言：javascript复制// 堆的数据个数
int HeapSize(Heap* hp);在“ Heap.c "源文件中写到：
代码语言：javascript复制// 堆的数据个数
int HeapSize(Heap* hp)
{
assert(hp);
//断言空指针
return hp->size;
}（9）检测堆是否为空 这个很简单
如果堆为空返回非零结果
如果不为空返回0
代码演示：（内有注释）
（其中 hp 是一个堆指针类型的指针，下同）
在“ Heap.h "头文件中写到：
代码语言：javascript复制// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
int HeapEmpty(Heap* hp);在“ Heap.c "源文件中写到：
代码语言：javascript复制// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
int HeapEmpty(Heap* hp)
{
assert(hp);
//断言空指针
return hp->size == 0;
}三、完整代码实现1. Heap.h用于存放用来放函数的声明和一些库函数的头文件
代码语言：javascript复制#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include
#include
#include
#include
#include
//重定义，方便修改类型
typedef int HPDataType;
//定义堆
typedef struct Heap
{
HPDataType* a; //数组指针
int size; //总元素
int capacity; //容量
}Heap;
// 堆的初始化
void HeapInit(Heap* hp);
// 堆的销毁
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 堆的删除
void HeapPop(Heap* hp);
// 取堆顶的数据
HPDataType HeapTop(Heap* hp);
// 堆的数据个数
int HeapSize(Heap* hp);
// 堆的判空
int HeapEmpty(Heap* hp);2. Heap.c用于用来放函数的定义(堆的主体)
代码语言：javascript复制#include"Heap.h"
// 堆的初始化
void HeapInit(Heap* hp)
{
assert(hp);
//断言空指针
hp->a = NULL;
hp->capacity = 0;
hp->size = 0;
//全部初始化置 0 / NULL
}
// 堆的销毁
void HeapDestory(Heap* hp)
{
assert(hp);
//断言空指针
free(hp->a);
//释放内存
hp->a = NULL;
hp->capacity = 0;
hp->size = 0;
//全部初始化置 0 / NULL
}
// 交换两个数的值
void Swap(HPDataType* x, HPDataType* y)
{
HPDataType tmp = *x;
*x = *y;
*y = tmp;
}
// 将尾插的元素向上调整
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(Heap* hp, HPDataType x)
{
assert(hp);
//断言空指针
if (hp->size == hp->capacity)
//当size=capacity时就表示空间不足，此时需要增容，故进入if语句
{
//先设置新变量，增容后再赋值
int newcapacity = hp->capacity == 0 ? 4 : 2 * hp->capacity;
//设置一个三目操作符判断原空间是否为 0
//当原空间为0时给空间开辟 4 字节；当原空间不为0时给空间增容 2倍
HPDataType* tmp = (HPDataType*)realloc(hp->a, newcapacity * sizeof(HPDataType));
//由于是在原空间的基础上给空间增容，故我们这里使用 realloc函数 增容
//增容大小为上面的 newcapacity *（类型大小）
if (tmp == NULL)
//加一个 if语句 防止增容失败
{
perror("realloc fail");
return;
}
//没有问题后就赋值
hp->a = tmp;
hp->capacity = newcapacity;
}
hp->a[hp->size] = x;
hp->size++;
AdJustUp(hp->a, hp->size - 1);
//插入完后就向上调整
}
// 将交换的元素向下调整
void AdJustDown(HPDataType* a, int parent, int size)
{
// 先假设左孩子小
int child = 2 * parent + 1;
while (child <= size - 1)
{
if (child + 1 <= size - 1 && a[child + 1] < a[child])
{
child++;
}
if (a[child] < a[parent])//若父亲大于孩子，父亲就要向下调整
{
Swap(&a[child], &a[parent]);
parent = child;
child = 2 * parent + 1;
}
else
{
break;
}
}
}
// 堆的删除（交换+头删+调整）
void HeapPop(Heap* hp)
{
assert(hp);
assert(hp->size > 0);
//断言空指针
//断言顺序表不能为空
Swap(&(hp->a[0]), &(hp->a[hp->size - 1]));
hp->size--;
//先将头部和尾部的值交换
//并且size--（类似删除尾部）
AdJustDown(hp->a, 0, hp->size);
//将头部的数据向下调整
}
// 取堆顶的数据
HPDataType HeapTop(Heap* hp)
{
assert(hp);
assert(hp->size > 0);
//断言空指针
//断言顺序表不能为空
return hp->a[0];
}
// 堆的数据个数
int HeapSize(Heap* hp)
{
assert(hp);
//断言空指针
return hp->size;
}
// 堆的判空
int HeapEmpty(Heap* hp)
{
assert(hp);
//断言空指针
return hp->size == 0;
}3. Test.c用于测试实现的堆的运行效果
（这里是小编在写代码时写的测试用例）
代码语言：javascript复制#include"Heap.h"
int main()
{
Heap H;
HeapInit(&H);
HeapPush(&H, 423);
HeapPush(&H, 234);
HeapPush(&H, 233);
HeapPush(&H, 44);
HeapPush(&H, 35);
HeapPush(&H, 6235);
while (!HeapEmpty(&H))
{
printf("%d ", HeapTop(&H));
HeapPop(&H);
}
printf("\n\n");
HeapDestory(&H);
return 0;
}结语本期资料来自于：
https://legacy.cplusplus.com/
OK，本期的堆详解到这里就结束了
若内容对大家有所帮助,可以收藏慢慢看,感谢大家支持
本文有若有不足之处，希望各位兄弟们能给出宝贵的意见。谢谢大家！！！
新人，本期制作不易希望各位兄弟们能动动小手，三连走一走！！！
支持一下（三连必回QwQ）