企业彩铃制作网站沈阳seo优化
🔥博客主页：小王又困了
📚系列专栏：数据结构
🌟人之为学，不日近则日退
❤️感谢大家点赞👍收藏⭐评论✍️
目录
一、二叉树的顺序结构
📒1.1顺序存储
📒1.2堆的性质
📒1.3堆的分类
二、堆的实现
📒2.1堆的创建
📒2.2堆的初始化
📒2.3堆的插入
📒2.4向上调整数据
📒2.5堆的删除
📒2.6向下调整数据
📒2.7堆的销毁
🗒️前言：
在上一期的文章中我们学习了一些二叉树的知识，也了解了堆的概念。堆是一颗完全二叉树，分为大堆和小堆，今天我们将实现堆的各种功能。
一、二叉树的顺序结构
📒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; }
本次的内容到这里就结束啦。希望大家阅读完可以有所收获，同时也感谢各位读者三连支持。文章有问题可以在评论区留言，博主一定认真认真修改，以后写出更好的文章。你们的支持就是博主最大的动力。