【数据结构】二叉树之堆的实现

🔥博客主页：小王又困了

📚系列专栏：数据结构

🌟人之为学，不日近则日退

❤️感谢大家点赞👍收藏⭐评论✍️

一、二叉树的顺序结构

📒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;}}
}