🗒️前言：
在上一期的文章中我们学习了一些二叉树的知识，也了解了堆的概念。堆是一颗完全二叉树，分为大堆和小堆，今天我们将实现堆的各种功能。
一、二叉树的顺序结构
📒1.1顺序存储
顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实使用中只有堆才会使用数组来存储。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。
📒1.2堆的性质
- 堆中某个节点的之总是不大于或不小于其父亲节点的值
- 堆是一颗完全二叉树
📒1.3堆的分类
- 小堆：树中任意一个父亲都小于等于孩子
- 大堆：树中任意一个父亲都大于等于孩子
二、堆的实现
📒2.1堆的创建
堆的逻辑结构是树形结构，是我们想象出来的，实际上我们操作的数组，所以堆的创建和顺序表的结构相同。
typedef int HPDateType; typedef struct Heap { HPDateType* a; int size; int capacity; }HP;
📒2.2堆的初始化
我们有两种初始化的方式，一种是在初始化阶段不开辟空间，在插入过程中进行扩容；另一种是在初始化阶段就开辟空间。
void HeapInit(HP* php) { assert(php); php->a = NULL; php->size = 0; php->capacity = 0; }
void HeapInit(HP* php) { assert(php); php->size = 0; php->capacity = 5; php->a = (HPDateType*)malloc(sizeof(HPDateType) * capacity); if (tmp == NULL) { perror("malloc"); exit(-1); } }
📒2.3堆的插入
堆是使用顺序结构的数组来存储的，我们使用尾插插入数据更方便，然后将数据调整到合适的位置。
void HeapPush(HP* php, HPDataType x) { assert(php); // 扩容 if (php->size == php->capacity) { int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2; HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newCapacity); 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); }
如图：在小堆中插入50，50比它的父亲小，所以要交换两数的位置。我们知道孩子的下标通过 parent=(child-1)/2 就可以得到父亲的下标，然后交换两数。
📒2.4向上调整数据
如果是小堆存储我们通过孩子的下标找到父亲，比较两数如果孩子小于父亲就交换，然后在向上比较，如果孩子不小于父亲就跳出循环。
void Swap(HPDataType* p1, HPDataType* p2) { HPDataType tmp = *p1; *p1 = *p2; *p2 = 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 = (parent - 1) / 2; } else { break; } } }
📒2.5堆的删除
我们使用挪动覆盖的方法删除根，会使关系混乱，剩下的值不一定是堆，而且效率很低。这里提供一种更好的方法，将根和最后一个值交换，然后删除，最后调整数据。
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); }
这里要注意有数据的时候才能删除，所以要加入 assert(php->size > 0) 进行判断。
📒2.6向下调整数据
如果是小堆存储我们要找到左右孩子中较小的数，然后与父亲交换，再找到下一层重复步骤，直到找到叶节点结束。
void AdjustDown(HPDataType* a, int n, int parent) { //默认左孩子是较小的 int child = parent * 2 + 1; while (child < n) { // 找出小的那个孩子 if (child + 1 < n && a[child + 1] < a[child]) { ++child; } if (a[child] < a[parent]) { Swap(&a[child], &a[parent]); // 继续往下调整 parent = child; child = parent * 2 + 1; } else { break; } } }
📒2.7堆的销毁
我们使用动态开辟内存，要及时释放空间并置为空指针，不然会造成数据泄露。
void HeapDestroy(HP* php) { assert(php); free(php->a); php->a = NULL; php->size = php->capacity = 0; }
本次的内容到这里就结束啦。希望大家阅读完可以有所收获，同时也感谢各位读者三连支持。文章有问题可以在评论区留言，博主一定认真认真修改，以后写出更好的文章。你们的支持就是博主最大的动力。
