【数据结构】堆——超详解！！！（包含堆的实现）
【数据结构】堆——超详解！！！（包含堆的实现）
前言
往期我们的学习中讲到了二叉树
它可以帮我们解决很多问题，而类似的数据结构还有很多
今天，我们就来聊聊——堆
一、堆是什么？
1. 堆的定义
堆：
上期我们讲讲到了二叉树，知道了完全二叉树以及非完全二叉树
而堆，就是一个完全二叉树，但在其基础上增加了一些东西，变得更加有序
2. 堆的分类
堆从排序的角度，被分为两类，一个是大堆，一个是小堆
- 大堆
在大堆中，任何一个父结点的值都要大于或等于子结点的值
（只是父亲与孩子之间的比较，与兄弟结点无关—）
如图，这就是一个大堆：
- 小堆
而在小堆中恰恰相反，任何一个子结点的值都要大于或等于父结点的值
（只是父亲与孩子之间的比较，与兄弟结点无关—）
如图，这就是一个小堆：
3. 堆的特点
由于在大堆中，任何一个父结点的值都要大于或等于子结点的值
在小堆中，任何一个子结点的值都要大于或等于父结点的值
故堆有一个很重要的特点：
在堆中，根结点的值最大或最小，故可通过堆来找极大值和极小值
二、堆的实现（小堆）
（本文实现的堆是小堆，但原理一样）
1. 用什么来实现？
想要实现堆，首先要想清楚要用什么实现堆
之前，我们讲了完全二叉树的存储，提到完全二叉树的编号是连续的，对于完全二叉树来说，我们可以用数组来进行存储，用下标来进行编号
而堆，就是一个完全二叉树，所以直接使用数组实现即可
综上所诉，使用数组的结构来实现堆更优
2. 实现思路
这里可以拿顺序表来做参考，往期我们详解了顺序表的实现，大家感兴趣的可以去看看
链接：【C语言】数据结构——顺序表超详解!!!（包含顺序表的实现)
与顺序表同理，堆的实现也应该有三名成员：
1.指向一个数组的指针
2.堆内的总元素
3.堆内的总容量
3. 代码实现
本文以创建一个 int 类型的堆为例
（1）创建头文件&源文件
之前在讲解扫雷游戏中我就提到:
在写复杂程序时要养成写多个头文件&源文件的好习惯，这样条理就很清晰也不会乱
如图:
创建了一个 “ Heap.h "头文件
用于存放用来放函数的声明和一些库函数的头文件
创建了一个 “ Heap.c "源文件
用于用来放函数的定义(堆的主体)
还有一个 ” Test.c "源文件
用于测试实现的堆的运行效果
（2）定义堆（定义）
首先我们要定义一个堆
代码演示：（内有注释）
（在头文件“ Heap.h "中写）
//重定义，方便修改类型typedefint HPDataType;//定义堆typedefstructHeap{ HPDataType* a;//数组指针int size;//总元素int capacity;//容量 }Heap;在定义堆的代码中，有两个需要注意的点：本文是以int类型为例，但如果以后要将堆的类型修改成char类型或是其他类型一个一个修改就很麻烦
所以我们重定义int类型为HPDataType,并将接下来代码中的int类型全部写成HPDataType
这是为了方便我们以后对类型进行修改，仅需将int改为其他类型即可在定义堆的同时重定义堆变量名为Heap方便以后使用
（3）堆的初始化（初始化）
定义完堆后，肯定要对堆进行初始化，内容全部置 0 / NULL代码演示：（内有注释）
（其中 hp 是一个堆指针类型的指针，下同）
在“ Heap.h "头文件中写到：
// 堆的初始化voidHeapInit(Heap* hp);在“ Heap.c "源文件中写到：
// 堆的初始化voidHeapInit(Heap* hp){assert(hp);//断言空指针 hp->a =NULL; hp->capacity =0; hp->size =0;//全部初始化置 0 / NULL}在写堆的实现的代码中，有一个很重要的点：
当我们函数在进行传参时，可能会传入空指针，而我们知道空指针是不能进行解引用的
故为了我们的代码更加健壮，可以加入assert 断言来判断是否符合条件，在之后的代码中也都有
关于更加详细的assert 断言介绍可参见下文：
【C语言】带你层层深入指针——指针详解3（野指针、assert等）
（4）堆的销毁（销毁）
在我们的程序运行完毕后，当然要对堆进行销毁，以免占用内存
代码演示：（内有注释）
（其中 hp 是一个堆指针类型的指针，下同）
在“ Heap.h "头文件中写到：
// 堆的销毁voidHeapDestory(Heap* hp);在“ Heap.c "源文件中写到：
// 堆的初始化voidHeapInit(Heap* hp){assert(hp);//断言空指针 hp->a =NULL; hp->capacity =0; hp->size =0;//全部初始化置 0 / NULL}// 堆的销毁voidHeapDestory(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 "头文件中写到：
// 堆的插入voidHeapPush(Heap* hp, HPDataType x);在“ Heap.c "源文件中写到：
（插入函数）
// 堆的插入（尾插+调整）voidHeapPush(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);}（向上调整函数）
// 将尾插的元素向上调整voidAdJustUp(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;}}}（交换函数）
// 交换两个数的值voidSwap(HPDataType* x, HPDataType* y){ HPDataType tmp =*x;*x =*y;*y = tmp;}（6）删除数据（出堆）
对于堆来说，要删除数据一般都是删除堆顶的元素
但是删除后想要调整回一个小堆就不容易了
所以我们采用一种间接删除的方式
方法：先将堆顶和堆尾的值交换，然后删除堆尾数据
此时相当于把之前的堆顶数据删除了
而且对于数组来说尾删是很简单的，只需要将总个数减一就行然后就开始处理首元素了，和尾插同理，需要调整，但这里是向下调整
由于我们建的是小堆，所以若父亲大于孩子，父亲就要向下调整，将父亲与孩子的值对调
直到父亲小于孩子，调整结束
代码演示：（内有注释）
（其中 hp 是一个堆指针类型的指针，下同）
在“ Heap.h "头文件中写到：
// 堆的删除voidHeapPop(Heap* hp);在“ Heap.c "源文件中写到：
（删除函数）
// 堆的删除（交换+头删+调整）voidHeapPop(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);//将头部的数据向下调整}（向下调整函数）
// 将交换的元素向下调整voidAdJustDown(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;}}}（交换函数）
// 交换两个数的值voidSwap(HPDataType* x, HPDataType* y){ HPDataType tmp =*x;*x =*y;*y = tmp;}（7）获取堆顶元素
这个很简单，直接用下标进行访问数据
再返回所对应的值
代码演示：（内有注释）
（其中 hp 是一个堆指针类型的指针，下同）
在“ Heap.h "头文件中写到：
// 取堆顶的数据 HPDataType HeapTop(Heap* hp);在“ Heap.c "源文件中写到：
// 取堆顶的数据 HPDataType HeapTop(Heap* hp){assert(hp);assert(hp->size >0);//断言空指针//断言顺序表不能为空return hp->a[0];}（8）获取堆的数据个数
这个很简单
直接返回所对应的值
代码演示：（内有注释）
（其中 hp 是一个堆指针类型的指针，下同）
在“ Heap.h "头文件中写到：
// 堆的数据个数intHeapSize(Heap* hp);在“ Heap.c "源文件中写到：
// 堆的数据个数intHeapSize(Heap* hp){assert(hp);//断言空指针return hp->size;}（9）检测堆是否为空
这个很简单
如果堆为空返回非零结果
如果不为空返回0
代码演示：（内有注释）
（其中 hp 是一个堆指针类型的指针，下同）
在“ Heap.h "头文件中写到：
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 intHeapEmpty(Heap* hp);在“ Heap.c "源文件中写到：
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 intHeapEmpty(Heap* hp){assert(hp);//断言空指针return hp->size ==0;}三、完整代码实现
1. Heap.h
用于存放用来放函数的声明和一些库函数的头文件
#pragmaonce#define_CRT_SECURE_NO_WARNINGS1#include<stdio.h>#include<stdlib.h>#include<assert.h>#include<sperror.h>#include<stdbool.h>//重定义，方便修改类型typedefint HPDataType;//定义堆typedefstructHeap{ HPDataType* a;//数组指针int size;//总元素int capacity;//容量 }Heap;// 堆的初始化voidHeapInit(Heap* hp);// 堆的销毁voidHeapDestory(Heap* hp);// 堆的插入voidHeapPush(Heap* hp, HPDataType x);// 堆的删除voidHeapPop(Heap* hp);// 取堆顶的数据 HPDataType HeapTop(Heap* hp);// 堆的数据个数intHeapSize(Heap* hp);// 堆的判空intHeapEmpty(Heap* hp);2. Heap.c
用于用来放函数的定义(堆的主体)
#include"Heap.h"// 堆的初始化voidHeapInit(Heap* hp){assert(hp);//断言空指针 hp->a =NULL; hp->capacity =0; hp->size =0;//全部初始化置 0 / NULL}// 堆的销毁voidHeapDestory(Heap* hp){assert(hp);//断言空指针free(hp->a);//释放内存 hp->a =NULL; hp->capacity =0; hp->size =0;//全部初始化置 0 / NULL}// 交换两个数的值voidSwap(HPDataType* x, HPDataType* y){ HPDataType tmp =*x;*x =*y;*y = tmp;}// 将尾插的元素向上调整voidAdJustUp(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;}}}// 堆的插入（尾插+调整）voidHeapPush(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);//插入完后就向上调整}// 将交换的元素向下调整voidAdJustDown(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;}}}// 堆的删除（交换+头删+调整）voidHeapPop(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];}// 堆的数据个数intHeapSize(Heap* hp){assert(hp);//断言空指针return hp->size;}// 堆的判空intHeapEmpty(Heap* hp){assert(hp);//断言空指针return hp->size ==0;}3. Test.c
用于测试实现的堆的运行效果
（这里是小编在写代码时写的测试用例）
#include"Heap.h"intmain(){ 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);return0;}结语
本期资料来自于：
OK，本期的堆详解到这里就结束了
若内容对大家有所帮助,可以收藏慢慢看,感谢大家支持
本文有若有不足之处，希望各位兄弟们能给出宝贵的意见。谢谢大家！！！
新人，本期制作不易希望各位兄弟们能动动小手，三连走一走！！！
支持一下（三连必回QwQ）
