启幕数据结构算法雅航新章，穿梭C++梦幻领域的探索之旅——二叉树序列构造 ...

   人无完人，持之以恒，方能见真我！！！
共同进步！！
  
  
一、堆的定义与结构

   堆的本质是一颗完全二叉树，只是它的要求比完全二叉树更加严酷，它要求每颗子树的根节点都是当前子树的最大值或最小值，当根节点是最大值时，它就是一个大根堆，当根节点是最小值时，它就是一个小根堆
    在上篇文章中我们也提到了，存储完全二叉树可以使用数组，存储非完全二叉树可以使用链表，而堆就是一种特殊的完全二叉树，所以堆的存储我们就使用数组，也就是次序表的情势，如图：
  

   我们将堆这个完全二叉树从上至下，从左至右的数据存放在数组中，至于怎么保证它每颗子树的根节点都是当前子树的最大值或最小值，我们在入堆和出堆的位置细讲，而次序表的结构我们已经很认识了，这里直接写出来：

1. typedef int HPDataType;
3. typedef struct Heap
4. {
5.         HPDataType* arr;
6.         int size;
7.         int capacity;
8. }HP;

复制代码

二、堆的实现

1.堆的初始化和烧毁

堆的初始化

   堆的初始化就是将数组置空，有用数据个数和容量大小置0，如下：

1. //堆的初始化
2. void HPInit(HP* php)
3. {
4.         assert(php);
5.         php->arr = NULL;
6.         php->size = php->capacity = 0;
7. }

复制代码

堆的烧毁

   堆的烧毁就是先判定数组是否为空，不为空就将它释放掉，因为数组的空间是我们向操作系统申请来的，不会主动释放，假如我们不主动释放就会造成内存泄漏，最后我们将数组置空，有用数据个数和容量大小置0，如下：

1. //销毁
2. void HPDestroy(HP* php)
3. {
4.         assert(php);
5.         if (php->arr)//不为空就释放
6.         {
7.                 free(php->arr);
8.         }
9.         php->arr = NULL;
10.         php->size = php->capacity = 0;
11. }

复制代码

2.向上调整算法和入堆

   接下来就是入堆操作，也就是向堆中插入数据，但是我们要知道，一样平常往数组中插入数据都是向数组尾部插入，那么是不是就会出现，本来堆的每颗子树的根节点都是当前子树的最大值或最小值，但是从尾部插入数据后会打破这个平衡，如图：
  

   可以看到，本来的堆是一个小根堆，但是我们插入一个5之后，它就不构成小根堆了，这个时候就要用到我们的向上调整算法，固然，假如插入一个数据后还依然构成小根堆的话，我们就不做处理即可
  向上调整算法

   在讲解向上调整算法时，我们就统一以小根堆为例，向上调整算法的本质就是将我们插入的数据当作孩子节点，让它和它的父节点举行比力
    那么有了孩子节点，怎么找到父节点呢？其实我们在上一篇讲过，父节点parent的下标等于(child-1)/2，找到父节点后，我们就看插入的数据是不是比它的父节点还小，假如是那么就直接举行互换，否则就不做操作，如图：
  

   但是我们发现互换一次后照旧没有构成小根堆，所以向上调整算法要求，只要我们做了互换，那么就让child走到parent，parent再走到新的child的父节点，继续举行比力，直到child为0，此时它就没有父亲节点了，停止向上调整，如图：
  

1. void Swap(HPDataType* p1, HPDataType* p2)
2. {
3.         HPDataType x = *p1;
4.         *p1 = *p2;
5.         *p2 = x;
6. }
8. //向上调整
9. void AdjustUp(HPDataType* arr,int child)
10. {
11.         //根据传来的孩子节点算父亲节点
12.         int parent = (child - 1) / 2;
13.         //child>0是循环条件,因为要保证数据是数组元素
14.         while (child > 0)
15.         {
16.                 //如果是建小堆，就是<
17.                 if (arr[child] < arr[parent])
18.                 {
19.                         Swap(&arr[child], &arr[parent]);
20.                         //更新父节点和子节点
21.                         child = parent;
22.                         parent = (child - 1) / 2;
23.                 }
24.                 else//child >= parent，不用交换
25.                 {
26.                         break;
27.                 }
28.         }
29. }

复制代码

  这里是建小根堆的写法，假如想要建大堆，那么将 小于 改成 大于 即可
  入堆

   有了向上调整算法我们入堆就很简单了，只需要将数据插入到数组最后，然后调用向上调整函数，就可以让我们的堆不被打乱
    但是我们同时要注意，插入数据之前要检查数组空间大小是否足够，假如不敷的话要举行扩容，如下：

1. //入堆
2. void HPPush(HP* php, HPDataType x)
3. {
4.         assert(php);
5.         //入堆前检查空间，不够就扩容
6.         if (php->size == php->capacity)
7.         {
8.                 //判断capacity是否相等于0，不相等就给2倍
9.                 php->capacity = php->capacity == 0 ? 4 : 2 * php->capacity;
10.                 //使用realloc初始化tmp数组为0
11.                 HPDataType* tmp = (HPDataType*)realloc(php->arr,sizeof(HPDataType) *(php->capacity));
12.                 if (NULL == tmp)
13.                 {
14.                         perror("realloc fail\n");
15.                         return;
16.                 }
17.                 php->arr = tmp;
18.                 php->capacity *= 2;//这一步不要忘记
19.         }
20.         //判断空间后，存放数据
21.         php->arr[php->size] = x;
22.         //向上调整
23.         AdjustUp(php->arr, php->size);
24.         php->size++;
25. }

复制代码

3.向下调整算法和出堆顶数据

   在正式相识向下调整算法和出堆顶数据之前，首先我们要知道堆删除数据是删除堆顶的数据，也就是下标为0的数据，因为堆顶的数据是最特殊的，它是整个堆最大或最小的值，我们在堆的应用会讲到它的用法
    那么相识了这一点之后，我们再来想想怎么删除堆顶数据，假如直讨论删的话，那么之前堆的结构会完全乱套，我们画个图就知道了，以小根堆为例，如下：
  

   可以看到假如我们直接对堆举行头删的话，整个堆的数据都被打乱了，结构也变乱了，我们要调整的话也无从下手，接下来我们就来先容删除堆顶数据的精确做法
    删除堆顶数据的精确做法就是，互换最后一个数据和堆顶数据，然后让size- -，如许我们就只会影响最后一个数据和堆顶数据，不会影响其它节点，如图：
  

   颠末上面的操作，我们就可以发现，我们删除了堆顶数据，只是说将堆中的最后一个数据移到了堆顶，但是也只改变了堆中的最后一个数据的位置，不至于像头删那样将整个堆的结构打乱
    那么将堆中的最后一个数据放到了堆顶，此时堆很大概不是一个有用的堆，所以我们需要从堆顶向下调整整个堆，我们需要一个向下调整算法
  向下调整算法

   颠末上面的分析，我们知道堆删除数据后，堆顶元素大概不符合堆的要求，所以我们要从堆顶开始向下调整，要注意的是，我们举例都是以小根堆为例
    具体方法就是，将堆顶当作父节点parent，根据2*parent找到它的孩子节点child，最后让父节点和孩子节点举行比力，假如孩子节点更小就举行互换，然后让父亲走到孩子的位置，孩子再走到新父亲的孩子节点
    假如孩子节点比父节点更大的话就不做修改，跟我们的向上调整算法雷同，但是我们要注意一个点，我们在向下调整的时候，需要看当前父节点的左孩子和右孩子谁小，父节点要和小的那个孩子举行互换，为什么呢？
    因为假如父节点和较大的那个孩子举行互换的话，较大的那个孩子就成了堆顶，另一个较小的孩子就比堆顶小，不满意小根堆的条件，如图：
  

   可以发现，在这种情况下，我们颠末互换后并不符合堆的要求，因为本来的右孩子较小，但是父节点是和左孩子举行互换的，导致较大的左孩子到了堆顶，不符合堆的要求
    所以我们在举行向下调整时，找到左孩子child后，还要先判定一下左右孩子谁更小，假如左孩子更小就不需要做更改，假如右孩子更小就让child++，如许就可以让child走到更小的右孩子了(注意左右孩子的关系，右孩子比左孩子的下标大1)
    那么有了精确的思绪之后我们重新走一遍上面的过程，看看有没有题目，如图：
  

   通过一系列的画图分析，我们直接根据思绪写出对应的代码即可，如下：

1. //向下调整--多传一个n，是循环的结束条件
2. void AdjustDown(HPDataType* arr, int parent, int n)
3. {
4.         //根据父节点算出左孩子
5.         int child = parent * 2 + 1;
6.         while (child < n)//向下调整不能越界
7.         {
8.                 //如果右孩子存在,并且比左孩子小
9.                 if (child + 1 < n && arr[child + 1] < arr[child])
10.                 {
11.                         child++;//就让孩子变成右孩子
12.                 }
13.                 //孩子小于父亲就交换
14.                 if (arr[child] < arr[parent])
15.                 {
16.                         Swap(&arr[child], &arr[parent]);
17.                         //交换后，更新child 、 parent
18.                         parent = child;
19.                         child = 2 * parent + 1;
20.                 }
21.                 else
22.                 {
23.                         //父节点小于子节点
24.                         break;
25.                 }
26.         }
27. }

复制代码

出堆

   上面我们其实已经完备讲解了出堆的过程，这里我们再次回顾一下，出堆就是指删除堆中的堆顶数据，方法就是互换堆顶和最后一个数据，让size- -，间接删除了堆顶数据，然后最后一个数据到了堆顶，再对它举行向下调整即可
   那么有了思绪我们就可以直接写代码了，如下：

1. //出堆顶元素
2. void HPPop(HP* php)
3. {
4.         assert(php);
5.         assert(!HPEmpty(php));//堆不为空才出堆
6.         //删除数据---size是总大小，所以-1是最后一个元素的下标
7.         Swap(php->arr[0], &php->arr[php->size-1]);//交换首尾元素
8.         php->size--;
10.         //交换删除后，得到新首尾，向下调整
11.         AdjustDown(php->arr, 0, php->arr);//0是父节点
12. }

复制代码

4.堆的有用数据个数和判空

堆的有用数据个数

   堆的有用数据个数由size记录，直接返回size即可

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

复制代码

堆的判空

   堆的判空就是判定堆的有用数据个数是否为0，也是跟size相关

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

复制代码

5.取堆顶数据

   取堆顶数据就是取堆中下标为0位置的数据

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

复制代码

三、堆的源码

1. #include <stdio.h>#include <errno.h>#include <assert.h>#include <stdlib.h>#include <stdbool.h>typedef int HPDataType;
3. typedef struct Heap
4. {
5.         HPDataType* arr;
6.         int size;
7.         int capacity;
8. }HP;
9. #define _CRT_SECURE_NO_WARNINGS 1#include "Heap.h"//初始化void HPInit(HP* php){        assert(php);        php->arr = NULL;        php->size = php->capacity = 0;}//销毁
10. void HPDestroy(HP* php)
11. {
12.         assert(php);
13.         if (php->arr)//不为空就释放
14.         {
15.                 free(php->arr);
16.         }
17.         php->arr = NULL;
18.         php->size = php->capacity = 0;
19. }
20. void Swap(HPDataType* p1, HPDataType* p2)
21. {
22.         HPDataType x = *p1;
23.         *p1 = *p2;
24.         *p2 = x;
25. }
27. //向上调整
28. void AdjustUp(HPDataType* arr,int child)
29. {
30.         //根据传来的孩子节点算父亲节点
31.         int parent = (child - 1) / 2;
32.         //child>0是循环条件,因为要保证数据是数组元素
33.         while (child > 0)
34.         {
35.                 //如果是建小堆，就是<
36.                 if (arr[child] < arr[parent])
37.                 {
38.                         Swap(&arr[child], &arr[parent]);
39.                         //更新父节点和子节点
40.                         child = parent;
41.                         parent = (child - 1) / 2;
42.                 }
43.                 else//child >= parent，不用交换
44.                 {
45.                         break;
46.                 }
47.         }
48. }
49. //入堆void HPPush(HP* php, HPDataType x){        assert(php);        //入堆前检查空间，不敷就扩容        if (php->size == php->capacity)        {                //判定capacity是否相称于0，不相称就给2倍                php->capacity = php->capacity == 0 ? 4 : 2 * php->capacity;                //使用realloc初始化tmp数组为0                HPDataType* tmp = (HPDataType*)realloc(php->arr,sizeof(HPDataType) *php->capacity);                if (NULL == tmp)                {                        perror("realloc fail\n");                        return;                }                php->arr = tmp;                php->capacity *= 2;//这一步不要忘记        }        //判定空间后，存放数据        php->arr[php->size] = x;        //向上调整        AdjustUp(php->arr, php->size);        php->size++;}//向下调整--多传一个n，是循环的结束条件
50. void AdjustDown(HPDataType* arr, int parent, int n)
51. {
52.         //根据父节点算出左孩子
53.         int child = parent * 2 + 1;
54.         while (child < n)//向下调整不能越界
55.         {
56.                 //如果右孩子存在,并且比左孩子小
57.                 if (child + 1 < n && arr[child + 1] < arr[child])
58.                 {
59.                         child++;//就让孩子变成右孩子
60.                 }
61.                 //孩子小于父亲就交换
62.                 if (arr[child] < arr[parent])
63.                 {
64.                         Swap(&arr[child], &arr[parent]);
65.                         //交换后，更新child 、 parent
66.                         parent = child;
67.                         child = 2 * parent + 1;
68.                 }
69.                 else
70.                 {
71.                         //父节点小于子节点
72.                         break;
73.                 }
74.         }
75. }
76. //判空
77. bool HPEmpty(HP* php)
78. {
79.         return php->size == 0;
80. }
81. //出堆顶元素
82. void HPPop(HP* php)
83. {
84.         assert(php);
85.         assert(!HPEmpty(php));//堆不为空才出堆
86.         //删除数据---size是总大小，所以-1是最后一个元素的下标
87.         Swap(php->arr[0], &php->arr[php->size-1]);//交换首尾元素
88.         php->size--;
90.         //交换删除后，得到新首尾，向下调整
91.         AdjustDown(php->arr, 0, php->arr);//0是父节点
92. }
93. //堆的有效数据个数
94. int HPSize(HP* php)
95. {
96.         assert(php);
97.         return php->size;
98. }
99. //取堆顶元素
100. HPDataType HPTop(HP* php)
101. {
102.         assert(php);
103.         return php->arr[0];
104. }

复制代码

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