【数据结构】-向上调整算法和向下调整算法
作者：小树苗渴望变成参天大树
作者宣言：认真写好每一篇博客
作者gitee:gitee
如 果 你 喜 欢 作 者 的 文 章 ，就 给 作 者 点 点 关 注 吧！
堆
前言
今天我们来堆，堆是建立再有二叉树基础的前提下去学习的，采用的是二叉树的顺序存储方式，所以结构类似于满二叉树，会介绍堆的概念，以及模拟一个堆出来，本篇知识量有一点大，希望读者可以耐心的阅读下去，并且真正学会堆
一、堆的概念及结构
如果有一个关键码的集合K = { ， ， ，…， }，把它的所有元素按完全二叉树的顺存储方式存储在一个一维数组中，并满足： <= 且 <= ( >= 且 >= ) i = 0，1，2…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
堆的性质：
1.堆中某个节点的值总是不大于或不小于其父节点的值；
2.堆总是一棵完全二叉树。
3.堆顶一定是整个堆中最大或者最小的数据
我们只需要看堆的性质即可
我们来看一下两种类型的堆
看到现在我们要掌握什么是堆，什么是大根堆，什么是小根堆，以及怎么通过堆写成数组的形式，怎么通过数组来写成堆的形式
注意：堆里面的元素如果都相等的话，即可以看成大根堆，也可以看成小根堆
二、堆的创建（以大根堆为例）
我们刚才说过对于堆我们采取数组的方式来存储，还要满足可以往堆里面插入和删除数据时必须还得是堆的情况，我们采取顺序表的创建方式来创建堆
typedef int HPDataType;typedef struct Heap{HPDataType* a;//定义一个数组int size;//数组里面的有效数据个数int capacity;//此时数组容量大小}Heap;初始化和顺序表初始化一样：
void HPInit(Heap* php){php->a = (HPDataType*)malloc(sizeof(HPDataType) * 4);if (php->a == NULL){perror("malloc:");return;}php->size = 0;php->capacity = 4;}我们重点来介绍堆的插入和删除
三、堆的插入
我们插入数组的树必须保证原数组依然是堆，这就很有难度，我们先来看图讲解：
我们采取的是向上调整算法，肯定是先插入左孩子，再插入右孩子，所以插入的是右孩子不必考虑左孩子的值是否比父亲大等情况，我们只需要把插入的孩子和父亲比较就好了，当parent<0就结束，没有交换的时候表示已经是堆了，因为你再插入的之前他就是一个堆了
我们来看向上调整算法代码：
void Swap(HPDataType* p1, HPDataType* p2){HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;}void AdjustUp(HPDataType* a, int child)//传入的数组和插入的孩子再数组的下标{assert(a);int parent = (child - 1) / 2;//找到父亲结点对应的下标while (child > 0){if (a[parent] < a[child])//以大根堆为例，小根堆换一下符号即可{Swap(&a[parent], &a[child]);//交换child = parent;parent = (child - 1) / 2;//迭代}else{break;}}}因为都是一步步的向上进行调整，所有就叫向上调整算法
我们看堆的插入:
void HeapPush(Heap* php, HPDataType x){assert(php);if (php->size == php->capacity){HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * 2 * php->capacity);if (tmp == NULL){perror("realloc:");return;}else{php->a = tmp;php->capacity *= 2;}}php->a[php->size++] = x;//先插入，再把数组弄成堆的形式AdjustUp(php->a, php->size - 1);//向上调整算法}四、堆的删除
我们来想一下，堆的删除，应该还是删除那一个数据，是堆头还是堆尾，我们可以来想想，如果删除堆尾，有什么意义，即不一定是最大的数据，也不是最小的数据，没有什么意义，所以我们选择删除堆头的数据，那我们怎么去删除呢
有的人会想，再顺序表的时候，我们进行头删的时候，把前面的数据直接往前面挪一位，所以我们再堆的时候可不可以也这样搞，我们来画图看看：
我们发现采取挪数据的方式并不可取，父亲与孩子的关系全部乱了，那我们应该怎么去解决删数据的问题呢？？
我们想到一种方法，因为插入数据是在尾部插入，插入之前是堆，不影响，那我们再删除的时候再从尾部删除不就可以了，但是我要删除的数据是堆顶的数据啊，怎么删除尾部的呢，我们可以交换一下，那交换了这个堆可能就不是堆了，但是堆里面的结点的那个对应关系是不是没有破坏，我们重新调整就好了
来看图：
我们看到我们采取的向下天正算法，把交换好的数据重新调整成堆，我们来直观的看一下向下调整算法的代码
void Swap(HPDataType* p1, HPDataType* p2){HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;}void AdjustDown(HPDataType* a, int n, int parent){int child = parent * 2 + 1;//假设左孩子大while (child<n){if (child + 1 < n && a[child] < a[child + 1]){child += 1;}if (a[parent] < a[child]){Swap(&a[parent], &a[child]);parent = child;child = parent * 2 + 1;}else{break;}}}不会的可以走读一下代码看看是怎么实现的
我们来看一下删除的完整代码：
void HeapPop(Heap* php){assert(php);Swap(&php->a[0], &php->a[php->size - 1]);php->size--;AdjustDown(php->a, php->size, 0);//因为都是从堆顶调整，所以parent传的就是0}注意：向上调整算法和向下调整算法都有一个前提条件，被调整的那个结点，左右子树都必须是堆
对于堆的两款大骨头我们几乎啃完了，接下来大部分都是顺序表玩生下来的操作了
五、堆顶的元素
HPDataType* HeapTop(Heap* php){assert(php);return php->a[0];}六、判断堆是否为空
bool HeapEmtpy(Heap* php){assert(php);return php->size == 0;}七、堆里有多少元素
int HeapSize(Heap* php){assert(php);return php->size;}八、代码测试
int main(){Heap php;HPInit(&php);HeapPush(&php,1);HeapPush(&php, 2);HeapPush(&php, 34);HeapPush(&php, 4);HeapPush(&php, 23);HeapPush(&php, 16);HeapPush(&php, 7);while (!HeapEmtpy(&php)){printf("%d ", HeapTop(&php));HeapPop(&php);}}
我们看到我们手动模拟出来一个堆了，相信大家学到这里对堆有了不一样的理解
完整代码：
#include"Heap.h"void HPInit(Heap* php){php->a = (HPDataType*)malloc(sizeof(HPDataType) * 4);if (php->a == NULL){perror("malloc:");return;}php->size = 0;php->capacity = 4;}void Swap(HPDataType* p1, HPDataType* p2){HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;}void AdjustUp(HPDataType* a, int child){assert(a);int parent = (child - 1) / 2;while (child > 0){if (a[parent] < a[child]){Swap(&a[parent], &a[child]);child = parent;parent = (child - 1) / 2;}else{break;}}}void HeapPush(Heap* php, HPDataType x){assert(php);if (php->size == php->capacity){HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * 2 * php->capacity);if (tmp == NULL){perror("realloc:");return;}else{php->a = tmp;php->capacity *= 2;}}php->a[php->size++] = x;AdjustUp(php->a, php->size - 1);//向上调整算法}void AdjustDown(HPDataType* a, int n, int parent){int child = parent * 2 + 1;//假设左孩子大while (child<n){if (child + 1 < n && a[child] < a[child + 1]){child += 1;}if (a[parent] < a[child]){Swap(&a[parent], &a[child]);parent = child;child = parent * 2 + 1;}else{break;}}}void HeapPop(Heap* php){assert(php);Swap(&php->a[0], &php->a[php->size - 1]);php->size--;AdjustDown(php->a, php->size, 0);}HPDataType* HeapTop(Heap* php){assert(php);return php->a[0];}bool HeapEmtpy(Heap* php){assert(php);return php->size == 0;}int HeapSize(Heap* php){assert(php);return php->size;}#include来源地址：https://blog.csdn.net/qq_69369227/article/details/129758954
免责声明：
① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的，并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据，供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。
② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
