嗨~大家好，这里是春栀怡铃声的博客~
“做你害怕的事，然后发现，不过如此~”
今天接着讲解堆相关内容，坐稳发车喽~ 我们以创建小堆为栗子
目录
堆的实现
创建3个文件
堆的创建
堆的初始化
交换函数
堆的向上调整
堆的插入
堆向下调整
堆的删除
堆的销毁
取堆顶的数据
堆的判空
堆的实现
创建3个文件
首先需要在vs2022创建3个文件
①Heap.h 堆的头文件—>包含堆的结构 堆进行一系列操作的函数声明 三个文件中所有有用到的头文件
②Heap.c 包含堆进行一系列操作的函数定义
③text.c 检测堆是否正确执行
堆的创建
堆是完全二叉树，建立堆
typedef int HPDataType;
typedef struct Heap
{
int capacity;
int size;
HPDataType* a;
}HP;
capacity—>存储容量（空间大小）
size—>当前元素个数
HPDataType * a—->a指向存放HPDataType这个类型的数组
我们在这里typedef int HPDataType 是为了如果之后顺序表中储存的数据是char 等其他类型的数据，只需要把这里的int 改为char 即可，无需大幅度的修改。
typedef struct HPDataType HP是为了之后定义指向顺序表的指针可以写HP*a，省的写 struct HPDataType*a
堆的初始化
//初始化
void HPInit(HP* php)
{
assert(php);
php->a = NULL;
php->capacity = php->size = 0;
}
HP*php —>将指向堆的地址传参，只有将地址传参，才能改变数值
php->capacity=0—->堆中存储空间置为0
php->size=0—–>堆中有效数据个数也置为0
php->a=NULL—–>堆中指向存放数据的数组的指针置为空
交换函数
void Swap(HPDataType* p1, HPDataType* p2)
{
HPDataType tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
注意看这里传参传的是 HPDataType* p1 HPDataType* p2 ，而不是HP*p1 HP*p2
具体原因先瞒着，一会儿告诉你们~
堆的向上调整
//向上调整
void AdjustUp(HPDataType* a,int child)
{
int preant = (child – 1) / 2;
while (child > 0)
{
if (a[child] < a[preant])
{
Swap(&a[child], &a[preant]);
child = preant;
preant = (child – 1) / 2;
}
else
{
break;
}
}
}
图解示意：
现在 5 作为新插入的数据，需要保持原来小堆的性质（子结点都小于父结点，兄弟结点没有限制）
需要向上调整，显然，5<56，需要将5和56互换位置，继续观察
继续观察5<10 需要继续交换5和10
根据代码来进行向上调整，
①已知孩子结点，可以求出父结点。父亲结点的坐标为 preant = (child – 1) / 2
由于调整的是孩子结点，传参传递的是孩子结点，通过孩子结点求出父结点
②根结点的下标是0，新插入的孩子结点需要一直比较，直到和根结点比较完才调整结束
此处需要while 循环
③如果孩子结点的值小于父结点，（当然，结点的值储存在数组中） 交换！并且让child 转移位置到 preant 结点位置 重新求父结点，继续while循环 成功实现子结点向上移动
④如果如果孩子结点的值大等于父结点，则直接 break
堆的插入
//插入
void HPPush(HP* php, HPDataType x)
{
assert(php);
if (php->size == php->capacity)
{
int newcapacity = php ->capacity == 0 ? 4 : 2 * php->capacity;
HPDataType* cur = (HPDataType*)realloc(php->a, newcapacity * sizeof(HPDataType));
if (cur == NULL)
{
perror("realloc fail");
return;
}
php->a = cur;
php->capacity = newcapacity;
}
php->a[php->size] = x;
php->size++;
AdjustUp(php->a, php->size-1);
}
①如果capacity==0，newcapacity*2==0,需要先用三目操作符避免出现扩容后还是0的情况~
int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
如果php->capacity==0,直接赋值给newcapacity==4, 如果不等于0，就使用2*php->capacity的值赋值给newcapacity~
②动态申请内存时，注意怎么写？
HPDataType* cur = (HPDataType*)realloc(php->a,newcapacity * sizeof(HPDataType));
申请的内存是用来存放数据的，扩充的是存放 HPDataType这个类型 的数组，所以用realloc 在原来php->a这个数组的基础上扩充 ，自然realloc需要强制类型转换成 (HPDataType*) ，并且是newcapacity*sizeof(HPDataType) 新扩充出来的空间要存储 HPDataType 类型，所以要算sizeof(HPDataType)~
③不要忘记检验有没有动态申请成功呢~
if (cur == NULL) { perror("malloc"); exit(1); }
④将cur赋值给php->a, newcapacity赋值给php->capacity
插入过程：
①assert(php) 断言堆不能为空
实现原理
①php->a[php->size]=x;
②php->size++;
这里size代表有效数据的个数，我们数组的下标是从0开始计数的，正好size对应的就是数组空着的位置~
最重要的是！调用向上调整函数，保证原来小堆的性质不被新插入的值改变
堆向下调整
void AdjustDown(HPDataType* a,int n,int preant)
{
int child = preant * 2+1;
while (child<n) //buhui
{
if (child + 1 < n && a[child+1] < a[child])
{
++child;
}
if (a[child] < a[preant])
{
Swap(&a[child], &a[preant]);
preant = child;
child = preant * 2 + 1;
}
else
{
break;
}
}
}
①已知父结点，可以求出子结点。子结点的坐标为 child = preant * 2+1
由于调整的是父结点，传参传递的是父结点，通过父结点求出子结点
②根结点的下标是0，传入的父亲结点从上往下调整，直到到最后结点
此处需要while 循环
③由于向下调整，我们不清楚是不是 左孩子的值小于右孩子 ，我们采用假设法
假设左孩子结点的值小于右孩子， 我们交换左孩子和父结点
右孩子更小，那就让child+1 (前提是右孩子存在并且右孩子小于左孩子)
如果孩子小于父结点 ，交换！
并且让preant 转移位置到 child结点位置 重新求子结点，继续while循环 成功实现父结点向下移动
④如果如果孩子结点的值大等于父结点，则直接 break
堆的删除
//删除
void HPPop(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);
}
注意！堆删除，删除的是根结点
①assert断言，堆不为空，尾删时，还需要判断堆的有效数据为不为空
②先交换根结点与最后的叶子节点，接着删除叶子结点 让size–
传入根结点 进行向下调整
堆的销毁
//销毁
void HPDestory(HP* php)
{
assert(php);
free(php->a);
php->a = NULL;
php->capacity = php->size = 0;
}
需要判断一下堆是否为空，为空就不用进行释放操作了
将php->a置为NULL，php->capacity php->size都置为0
销毁完成！
取堆顶的数据
HPDataType HPTop(HP* php)
{
assert(php);
assert(php->size>0);
return php->a[0];
}
堆顶数据就是根结点，先要判断有没有堆，还要继续判断堆不为空，最后直接取出根结点数据即可
堆的判空
//判空
bool HPEmpty(HP* php)
{
assert(php);
return php->size == 0;
}
感谢花时间阅读这篇内容！
如果觉得有价值，欢迎点赞支持、收藏备用，或分享给同行。你的认可，是我持续输出高质量内容的最大动力。
我们下期再见喽！！！
