【数据布局】堆

[color=sky blue]博主的博客个人主页~
[color=sky blue]博主的数据布局专栏~

上期博客我们先容了树，本期我们来实现一种特殊的二叉树—堆。[color=sky blue]上期博客，食用请点击~
一、堆

1.1 堆的概念与存储布局

堆是一种特殊的完全二叉树数据布局，堆分为大根堆(大顶堆)和小根堆(小顶堆)，在大根堆中，每个节点的值都大于或等于其左右子节点的值；在小根堆中每个节点的值都小于或等于其左右节点的值。

完全二叉树适合用数组存储，它的节点排列非常规律，除最后一层外，每一层都是满的，且最后一层节点靠左对齐，用数组储存时，可根据根节点在数中的位置与数组下标的对应关系举行高效的访问和操作。因此我们将用数组来实现堆这一数据布局。
堆的性子：

• 堆中某个结点的值总是不大于或不小于其父结点的值；
  
• 堆总是⼀棵完全二叉树。
  完全二叉树的性子：
  对于具有 n 个结点的完全二叉树，如果按照从上到下从左到右的数组顺序对全部结点从0 开始编号，则对于序号为 i 的结点有：
  
• 若 i>0，i 位置结点的双亲序号：(i-1)/2 ；若i=0，i 为根结点编号，无双亲结点。
  
• 若 2i+1<n，左孩子序号： 2i+1；若2i+1>=n 无左孩子。
  
• 若 2i+2<n，右孩子序号： 2i+2；若2i+2>=n 无右孩子。
  

以上性子非常紧张，只有知道以上性子我们才华操作实现堆。(以上性子读者可以通过上面给出的两幅图来验证，如有疑问，请在评论区留言。)
二、堆的实现

2.1 堆的布局界说

1. typedef int HPDataType;
2. typedef struct Heap
3. {
4.         HPDataType* arr;
5.         int size;    //有效数据个数
6.         int capacity;//容量大小
7. }HP;

复制代码

由于使用数组实现堆，所以我们这边需要知道数组中存放了多少的有效数据size和数组的容量大小capacity，它的布局和顺序表的布局相似。
2.2 堆的初始化与销毁

由于初始化和销毁和顺序表的方式雷同，所以我们就直接给出代码了，关于顺序表读者可以点击这个观看：【数据布局】顺序表
初始化：

1. void HPInit(HP* php)
2. {
3.         php->arr = NULL;
4.         php->capacity = php->size = 0;
5. }

复制代码

销毁：

1. void HPDestroy(HP* php)
2. {
3.         if (php->arr)
4.         {
5.                 free(php->arr);
6.         }
7.         php->arr = NULL;
8.         php->size = php->capacity = 0;
9. }

复制代码

2.3 堆的打印

1. void HPPrint(HP* php)
2. {
3.         for (int i = 0;i < php->size;i++)
4.         {
5.                 printf("%d ", php->arr[i]);
6.         }
7.         printf("\n");
8. }

复制代码

2.4堆的插入

在插入的实现过程中，第一个要思量的题目就是数组的容量满了没有，如果满了，我们要增容，所以我们起首会判断容量够不够的题目，其次，堆这一数据布局，不像顺序表，它判断增不增容后，将数据今后一插就可以了，但堆它分为大根堆和小根堆，所以我们插入之后，如果不符合的话，还要调解数据的位置，来保证我们建的堆始终是大根堆大概小根堆。那么应该怎样调解呢？
我们以下面这幅图为例：：

我们接下来要插入一个数字99，很明显它比里面的全部数字都要大，但它现在在堆的末尾，所以，我们要将它向上调解(纵然我们建的是小根堆也一样，如果插入的数据比其他数据要小，我们仍旧要向上调解)。我们知道通过孩子节点可以找到父节点，假设孩子节点为i，那么父节点为(i-1)/2。

上图就是向上调解的过程图，由于我们插入的是之前调解好的堆，所以我们只需要将新插入的和父节点比较即可。在代码实现过程中我会将交换和向上调解操作单独封装成函数。
我们将以创建大根堆为树模：

1. void HPPush(HP* php, HPDataType x)
2. {
3.         assert(php);
4.         if (php->size == php->capacity)
5.         {
6.                 int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
7.                 HPDataType* set =(HPDataType*)realloc(php>arr,2*newcapacity*sizeof(HPDataType));
8.                 if (set == NULL)
9.                 {
10.                         perror("realloc fail!");
11.                         return 1;
12.                 }
13.                 php->arr = set;
14.                 php->capacity = newcapacity;
15.         }
16.         php->arr[php->size] = x;
17.         AdjustUp(php->arr, php->size);
18.         php->size++;
19. }

复制代码

向上调解：

1. void AdjustUp(HPDataType* arr, int child)
2. {
3.         int parent = (child - 1) / 2;
4.         while (child > 0)
5.         {
6.                 if (arr[child] > arr[parent])
7.                 {
8.                         Swap(&arr[child], &arr[parent]);
9.                         child = parent;
10.                         parent = (child - 1) / 2;
11.                 }
12.                 else
13.                         break;
14.         }
15. }

复制代码

交换：

1. void Swap(int* a, int* b)
2. {
3.         int tmp = *a;
4.         *a = *b;
5.         *b = tmp;
6. }

复制代码

测试代码：

1. #include "Heap.h"
3. void test()
4. {
5.         HP hp;
6.         HPInit(&hp);
7.         HPPush(&hp, 10);
8.         HPPush(&hp, 20);
9.         HPPush(&hp, 30);
10.         HPPush(&hp, 40);
11.         HPPush(&hp, 50);
12.         HPPush(&hp, 70);
13.         HPPrint(&hp);
14. }
16. int main()
17. {
18.         test();
19.         return 0;
20. }

复制代码

测试效果：

还原成堆：

可以看出，仍旧是大根堆。
2.5 堆的删除

在堆布局中删除数据只能删除堆顶，我们不能直接将堆顶删除，否则的话就不是堆布局了，它成为了两个子树，所以我们在删除的时候，要先将最后一个元素和堆顶交换位置，之后有效数据个数size减一，即可删除堆顶元素，但此时操作仍旧没有结束，因为经过我们的交换操作，我们创建的大根堆(小根堆)已经不是大根堆(小根堆)了，所以我们仍旧要对其举行调解，只不过这次是向下调解，别的我们还要判断删除操作时堆布局是否为空。
我们以一下这幅图为例：

调解过程：

判空函数：

1. //判空操作
2. bool HPEmpty(HP* php)
3. {
4.         assert(php);
5.         return php->size == 0;
6. }

复制代码

向下调解算法：

1. //向下调整
2. void AdjustDown(HPDataType* arr, int parent, int n)
3. {
4.         //假设左孩子大
5.         int child = parent * 2 + 1;
6.         while (child < n)
7.         {
8.                 if (child + 1 < n && arr[child] < arr[child + 1])
9.                 {
10.                         child++;
11.                 }
12.                 if (arr[child] > arr[parent])
13.                 {
14.                         Swap(&arr[child], &arr[parent]);
15.                         parent = child;
16.                         child = parent * 2 + 1;
17.                 }
18.                 else
19.                 {
20.                         break;
21.                 }
22.         }
23. }

复制代码

堆的删除：

1. //堆的删除
2. void HPPop(HP* php)
3. {
4.         assert(!HPEmpty(php));
5.         Swap(&php->arr[0], &php->arr[php->size - 1]);
6.         php->size--;
7.         AdjustDown(php->arr, 0, php->size);
8. }

复制代码

测试代码：

1. #include "Heap.h"
3. void test()
4. {
5.         HP hp;
6.         HPInit(&hp);
7.         HPPush(&hp, 10);
8.         HPPush(&hp, 20);
9.         HPPush(&hp, 30);
10.         HPPush(&hp, 40);
11.         HPPush(&hp, 50);
12.         HPPush(&hp, 70);
13.         HPPrint(&hp);
14.         HPPop(&hp);
15.         HPPop(&hp);
16.         HPPop(&hp);
17.         HPPrint(&hp);
18. }
20. int main()
21. {
22.         test();
23.         return 0;
24. }

复制代码

测试效果：

还原成子树：

2.6 取堆顶数据

1. //取堆顶数据
2. HPDataType HPTop(HP* php)
3. {
4.         assert(!HPEmpty(php));
5.         return php->arr[0];
6. }

复制代码

2.7求有效数据个数size

1. //求有效数据个数size
2. int HPSize(HP* php)
3. {
4.         assert(php);
5.         return php->size;
6. }

复制代码

  [color=sky blue]总结：
以上就是本期博客分享的全部内容啦！如果以为文章还不错的话可以三连支持一下，你的支持就是我进步最大的动力！
技术的探索永无止境! 道阻且长，行则将至！后续我会给各人带来更多优质博客内容，欢迎关注我的CSDN账号，我们一同成长！
(～￣▽￣)～

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。