DS：二叉树的顺序结构及堆的实现

                                       创作不易，兄弟们给个三连！！
一、二叉树的顺序存储

      顺序结构指的是利用数组来存储，一般只适用于表示完全二叉树，缘故原由如上图，存储不完全二叉树会造成空间上的浪费，有的人又会问，为什么图中空的位置不能存储呢？？缘故原由是我们必要根据数组的下标关系才气访问到对应的节点！！有以下两个下标关系公式：
1、父亲找孩子：leftchild=parent*2+1，rightchild=parent*2+2
2、孩子找父亲：parent=（child-1）/2   要注意，这边无论用左孩子算还是右孩子算都是可以的，因为一般俩说，（child-1）/2 由于int类型向下取整的特点，所以得到的结果都是一样的！！
      所以我们想要上面这种方式去访问节点，并且还不渴望有大量的空间浪费，现实中只有堆才会利用数组存储，二叉树的顺序存储中在物理上是一个数组，再逻辑上是一颗二叉树！！
二、堆的概念及结构

    现实中我们把堆（类似完全二叉树）利用顺序结构来存储，要注意这里的堆和操作体系虚拟历程地址空间中的堆是两回事，一个是数据结构，一个是操作体系中管理内存的一块地区分区。
   假如有一个关键码的集合k，我们将他的全部元素按照完全二叉树的存储逻辑放在一个一维数组中，则成为堆，根节点最大的堆叫做大堆，根节点最小的堆叫做小堆。 
堆的性子：
1、堆中某个节点的值总是不大于或不小于其父节点的值
2、堆总是一颗完全二叉树

注意：并不肯定有序 
三、堆的实现

假设我们实现小堆
3.1 相关结构体的创建

跟顺序表的形式是一样的，但是换了个名字

1. typedef int HPDataType;
2. typedef struct Heap
3. {
4.         HPDataType * a;
5.         int size;
6.         int capacity;
7. }Heap;

复制代码

3.2 堆的初始化

1. void HeapInit(Heap* php)
2. {
3.         assert(php);
4.         php->a = NULL;
5.         php->capacity = php->size = 0;
6. }

复制代码

3.3 堆的插入

堆的插入很简单，但是我们要包管堆插入后还能维持堆的形状

所以我们在插入后，还要举行向上调解，也就是孩子要根据下标关系找到自己的父亲去比力，小就互换

1. void HeapPush(Heap* php, HPDataType x)
2. {
3.         assert(php);
4.         //首先要判断是否需要扩容
5.         if (php->size == php->capacity)
6.         {
7.                 int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
8.                 HPDataType* temp = (HPDataType*)realloc(php->a,sizeof(HPDataType) * newcapacity);
9.                 if (temp == NULL)
10.                 {
11.                         perror("malloc fail");
12.                         exit(1);
13.                 }
14.             //扩容成功
15.                 php->a = temp;
16.                 php->capacity = newcapacity;
17.         }
18.      //扩容后，我们插入这个元素并size++
19.         php->a[php->size++] = x;
20.         //但是插入之后可能会破坏堆的结构，所以我们需要这个元素和他的父辈进行逐个比较，
21.         AdjustUp(php->a,php->size-1);//封装一个向上调整函数，传入数组和新加元素的下标
22. }

复制代码

3.4 向上调解算法

1. void AdjustUp(HPDataType* a, int child)
2. {
3.         assert(a);
4.     //通过孩子找父亲  parent=(child-1)/2
5.         int parent = (child - 1) / 2;
6.         //孩子和父亲开始比较，如果孩子小，就交换，如果孩子大，退出循环
7.         while (child>0)//如果孩子变成了根节点，就没有必要再找了，因为已经没有父母了
8.                 //如果用parent>=0来判断，那么由于（0-1）/2是-1/2，取整后还是0，就会一直死循环，所以必须用孩子来当循环条件
9.         {
10.                 if (a[child] < a[parent])//孩子小，交换
11.                 {
12.                         Swap(&a[child], &a[parent]);
13.                         //但是交换过后，可能还需要继续往上比，所以我们要让原来的父亲变成孩子，然后再找新的父亲进行比较
14.                         child = parent;
15.                         parent = (child - 1) / 2;
16.                 }
17.                 else//孩子大，退出
18.                         break;
19.         }
20. }

复制代码

注：这里的向上调解算法和后面向下调解算法我们都不用跟堆有关的接口，缘故原由就是这个算法的运用范围很广，可以用在堆排序以及top-k问题中！！
3.5 互换函数

1. void Swap(HPDataType* p1, HPDataType* p2)
2. {
3.         HPDataType temp = *p1;
4.         *p1 = *p2;
5.         *p2 = temp;
6. }

复制代码

3.6 堆的删除

         一般来说，假如直接删除堆的末了一个元素，实在是没什么意义的，一行代码就可以搞定，没必要封装什么函数，所以这里的堆的删除指的是删除根部的元素！！
        

1. void HeapPop(Heap* php)//一般来说，堆中的删除指的是删除根位置的数据
2. //如果直接删除根然后往前挪动一位，那么亲缘关系就会十分混乱，为了能够尽量在调整中减少对关系的改变
3. //我们将根部元素与最后一个元素进行交换之后再删除，此时的根是原先的最后一个元素
4. //然后将该元素进行向下调整（封装一个函数，传入数组、元素个数、）
5. {
6.         assert(php);
7.         assert(!HeapEmpty(php));//为空的话没有删除的必要
8.         Swap(&php->a[0], &php->a[php->size - 1]);
9.         php->size--;
10.         //开始向下调整
11.         AdjustDown(php->a, php->size,0);
12. }

复制代码

3.7 向下调解算法

1. void AdjustDown(HPDataType* a, int n,int parent)
2. {
3.         assert(a);
4.         //此时根部为原来的最后一个元素,往下比较
5.         //即通过父亲去找到自己的孩子，如果孩子比自己小，就得交换位置，如果孩子比自己大，就退出
6.         //但是因为父亲有一个左孩子parent*2+1，右孩子parent*2+2，我们选择孩子中较小的和自己交换
7.         int child = parent * 2 + 1;//假设左孩子比右孩子小
8.         while (child<n)//当child超出个数的时候结束
9.         {
10.                 if (child+1<n && a[child + 1]<a[child])//如果右孩子比左孩子小，假设错误，修正错误
11.                         //注意，一定不能写反，要注意只有左孩子没有右孩子的情况
12.                         child++;
13.                 if (a[child] < a[parent])//如果孩子小于父亲，交换
14.                 {
15.                         Swap(&a[child], &a[parent]);
16.                         //交换完后，让原来的孩子变成父亲，然后再找新的孩子
17.                         parent = child;
18.                         child = parent * 2 + 1;
19.                 }
20.                 else
21.                         break;//如果孩子大于等于父亲，直接退出
22.         }
23. }

复制代码

       在上述算法中，我们应用了先假设再推翻的方法，一开始我们先假设左孩子比力小，然后我们再给个条件判定，假如左孩子大于右孩子，假设不成立，再推翻，如许可以包管我们的child变量肯定是较小的孩子！！ 
       虽然这里的parent很明显是从a[0]开始，似乎不必要专门去传一个parent的参数，但是这也是为了之后的堆排序做预备！
3.8 取堆顶的数据

1. HPDataType HeapTop(Heap* php)
2. {
3.         assert(php);
4.         assert(!HeapEmpty(php));//为空的话没有取的必要
5.         return php->a[0];
6. }

复制代码

3.9 堆的数据个数

1. int HeapSize(Heap* php)
2. {
3.         assert(php);
4.         return php->size;
5. }

复制代码

3.10 堆的判空

1. bool HeapEmpty(Heap* php)
2. {
3.         assert(php);
4.         return php->size == 0;
5. }

复制代码

3.11 堆的销毁

1. void HeapDestory(Heap* php)
2. {
3.         assert(php);
4.         free(php->a);
5.         php->a = NULL;
6.         php->size = php->capacity = 0;
7. }

复制代码

3.12 堆的打印（测试）

我们要实现堆的打印，利用我们之前封装的函数，每获取一次堆顶元素就删除一次，直到堆删完就可以获取全部的元素了！！

1. #include"Heap.h"
2. int main()//该方法实现堆的顺序打印
3. {
4.         Heap hp;
5.         HeapInit(&hp);
6.         int a[] = { 55,100,70,32,50,60 };
7.         for (int i = 0; i < sizeof(a) / sizeof(int); i++)
8.                 HeapPush(&hp, a[i]);//不断进堆
9.         while (!HeapEmpty(&hp))
10.         {
11.                 int top = HeapTop(&hp);
12.                 printf("%d\n", top);
13.                 HeapPop(&hp);
14.         }
15.         HeapDestory(&hp);
16.         return 0;
17. }

复制代码

前面只是先创建一个堆，从while循环开始才是实现对堆的打印！！
   运行结果 ：32 50 55 60 70 100
            我们发现了一个情况：按原理来说堆只有父子节点之间有大小关系，兄弟之间没有的，但是我们末了打印出来的结果却完成了排序！！！下面我们来举行分析

     总之任何一个堆，我们都可以通过不断地pop去实现它的顺序打印！！堆排序后面会介绍！
四、堆实现的全部代码

4.1 Heap.h

1. #pragma once#include<stdio.h>#include<stdlib.h>#include<assert.h>#include<stdbool.h>typedef int HPDataType;
2. typedef struct Heap
3. {
4.         HPDataType * a;
5.         int size;
6.         int capacity;
7. }Heap;void Swap(HPDataType* p1, HPDataType* p2);//实现父亲和孩子的互换void AdjustUp(HPDataType* a, int child);//向上调解算法// 堆的初始化void HeapInit(Heap* php);// 堆的插入void HeapPush(Heap* php, HPDataType x);// 堆的删除void HeapPop(Heap* php);// 取堆顶的数据HPDataType HeapTop(Heap* php);// 堆的数据个数int HeapSize(Heap* php);// 堆的判空bool HeapEmpty(Heap* php);// 堆的销毁void HeapDestory(Heap* php);

复制代码

4.2 Heap.c

1. #include"Heap.h"//当前实现小堆void HeapInit(Heap* php)
2. {
3.         assert(php);
4.         php->a = NULL;
5.         php->capacity = php->size = 0;
6. }void Swap(HPDataType* p1, HPDataType* p2)
7. {
8.         HPDataType temp = *p1;
9.         *p1 = *p2;
10.         *p2 = temp;
11. }void AdjustUp(HPDataType* a, int child)
12. {
13.         assert(a);
14.     //通过孩子找父亲  parent=(child-1)/2
15.         int parent = (child - 1) / 2;
16.         //孩子和父亲开始比较，如果孩子小，就交换，如果孩子大，退出循环
17.         while (child>0)//如果孩子变成了根节点，就没有必要再找了，因为已经没有父母了
18.                 //如果用parent>=0来判断，那么由于（0-1）/2是-1/2，取整后还是0，就会一直死循环，所以必须用孩子来当循环条件
19.         {
20.                 if (a[child] < a[parent])//孩子小，交换
21.                 {
22.                         Swap(&a[child], &a[parent]);
23.                         //但是交换过后，可能还需要继续往上比，所以我们要让原来的父亲变成孩子，然后再找新的父亲进行比较
24.                         child = parent;
25.                         parent = (child - 1) / 2;
26.                 }
27.                 else//孩子大，退出
28.                         break;
29.         }
30. }void AdjustDown(HPDataType* a, int n,int parent)
31. {
32.         assert(a);
33.         //此时根部为原来的最后一个元素,往下比较
34.         //即通过父亲去找到自己的孩子，如果孩子比自己小，就得交换位置，如果孩子比自己大，就退出
35.         //但是因为父亲有一个左孩子parent*2+1，右孩子parent*2+2，我们选择孩子中较小的和自己交换
36.         int child = parent * 2 + 1;//假设左孩子比右孩子小
37.         while (child<n)//当child超出个数的时候结束
38.         {
39.                 if (child+1<n && a[child + 1]<a[child])//如果右孩子比左孩子小，假设错误，修正错误
40.                         //注意，一定不能写反，要注意只有左孩子没有右孩子的情况
41.                         child++;
42.                 if (a[child] < a[parent])//如果孩子小于父亲，交换
43.                 {
44.                         Swap(&a[child], &a[parent]);
45.                         //交换完后，让原来的孩子变成父亲，然后再找新的孩子
46.                         parent = child;
47.                         child = parent * 2 + 1;
48.                 }
49.                 else
50.                         break;//如果孩子大于等于父亲，直接退出
51.         }
52. }void HeapPush(Heap* php, HPDataType x)
53. {
54.         assert(php);
55.         //首先要判断是否需要扩容
56.         if (php->size == php->capacity)
57.         {
58.                 int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
59.                 HPDataType* temp = (HPDataType*)realloc(php->a,sizeof(HPDataType) * newcapacity);
60.                 if (temp == NULL)
61.                 {
62.                         perror("malloc fail");
63.                         exit(1);
64.                 }
65.             //扩容成功
66.                 php->a = temp;
67.                 php->capacity = newcapacity;
68.         }
69.      //扩容后，我们插入这个元素并size++
70.         php->a[php->size++] = x;
71.         //但是插入之后可能会破坏堆的结构，所以我们需要这个元素和他的父辈进行逐个比较，
72.         AdjustUp(php->a,php->size-1);//封装一个向上调整函数，传入数组和新加元素的下标
73. }void HeapPop(Heap* php)//一般来说，堆中的删除指的是删除根位置的数据
74. //如果直接删除根然后往前挪动一位，那么亲缘关系就会十分混乱，为了能够尽量在调整中减少对关系的改变
75. //我们将根部元素与最后一个元素进行交换之后再删除，此时的根是原先的最后一个元素
76. //然后将该元素进行向下调整（封装一个函数，传入数组、元素个数、）
77. {
78.         assert(php);
79.         assert(!HeapEmpty(php));//为空的话没有删除的必要
80.         Swap(&php->a[0], &php->a[php->size - 1]);
81.         php->size--;
82.         //开始向下调整
83.         AdjustDown(php->a, php->size,0);
84. }HPDataType HeapTop(Heap* php)
85. {
86.         assert(php);
87.         assert(!HeapEmpty(php));//为空的话没有取的必要
88.         return php->a[0];
89. }int HeapSize(Heap* php)
90. {
91.         assert(php);
92.         return php->size;
93. }
94. bool HeapEmpty(Heap* php)
95. {
96.         assert(php);
97.         return php->size == 0;
98. }void HeapDestory(Heap* php)
99. {
100.         assert(php);
101.         free(php->a);
102.         php->a = NULL;
103.         php->size = php->capacity = 0;
104. }

复制代码

4.3 test.c（测试）

1. #include"Heap.h"
2. int main()//该方法实现堆的顺序打印
3. {
4.         Heap hp;
5.         HeapInit(&hp);
6.         int a[] = { 55,100,70,32,50,60 };
7.         for (int i = 0; i < sizeof(a) / sizeof(int); i++)
8.                 HeapPush(&hp, a[i]);//不断进堆
9.         while (!HeapEmpty(&hp))
10.         {
11.                 int top = HeapTop(&hp);
12.                 printf("%d\n", top);
13.                 HeapPop(&hp);
14.         }
15.         HeapDestory(&hp);
16.         return 0;
17. }

复制代码

五、堆的应用

5.1 堆排序

要对数组排序前，我们要用堆排序，起首要建堆！
大家看看之前堆的打印时的测试代码逻辑的方法
就是我们得到一个数组，就先建堆，然后先把数组push进去，再pop出来，是可以实现有序的

但是现在我们的需求不是打印出来，而是将他排好序后放进数组里，所以们可以这么写：

1. void HeapSort(int* a, int n)
2. {
3.         HP hp;
4.         HeapInit(&hp);
5.         // N*logN
6.         for (int i = 0; i < n; ++i)
7.         {
8.                 HeapPush(&hp, a[i]);
9.         }
11.         // N*logN
12.         int i = 0;
13.         while (!HeapEmpty(&hp))
14.         {
15.                 int top = HeapTop(&hp);
16.                 a[i++] = top;
17.                 HeapPop(&hp);
18.         }
20.         HeapDestroy(&hp);
21. }

复制代码

 这个方法固然是可以的，但是很贫苦，缘故原由如下：
1、每次都要创建一个新的堆，然后再销毁，比力贫苦，而且空间复杂度比力高 
2、我通过把数组放进酿成堆，还要再把堆拷贝到数组中，数据的拷贝是很繁琐的！！
所以我们要思索一种方式避免数据的拷贝，所以就有了向上调解建堆和向下调解建堆的方法了！！
也就是我们在原数组的基础上直接建堆，然后向下调解排序即可，下面会详细介绍
5.1.1 向上调解建堆

 假设数组有n个元素

1. for (int i = 1; i < n; i++)
2. {
3.         AdjustUp(a, i);
4. }

复制代码

5.1.2 向下调解建堆

1. for (int i = (n-1-1)/2; i >= 0; i--)
2. {
3.         AdjustDown(a, n, i);
4. }

复制代码

5.1.3 堆排序的实现

那我们究竟选择向下建堆好还是向下建堆好呢？？我们来分析一下

所以我们发现向上调解建堆的时间复杂度大概是N*logN，而向下调解建堆的时间复杂度是N
实在们在推导的时候也能发现，向上调解建堆是节点多的情况调解得多，节点少的情况调解的少，次数是多*多+少*少 ，而向下调解建堆是节点多的情况调解得少，节点少的情况调解的多，次数是多*少+少*多，显然是向下调解建堆是更有优势的！！
     接下去我们建好堆，就要想着怎么去排序了，我们思索一下，之前我们对堆的打印时，不断pop打印出来有序结果的缘故原由是什么？？缘故原由就是pop函数里的向下调解算法！！每一次互换根节点和尾节点，将每个节点举行向下调解，末了就可以得到有序的
 

 因为我们之前实现的向下调解算法是小堆的，所以我们这边来实现一个降序的堆排序算法

1. void HeapSort(int* a, int n)
2. {
3.         //降序  建小堆
4.         //升序  建大堆
5.         for (int i = (n-1-1)/2; i >=0;i--)
6.                 AdjustDown(a, n, i);
7.         //开始排序   先交换向下调整
8.         int end = n - 1;
9.         while (end >= 0)
10.         {
11.                 Swap(&a[0], &a[end]);
12.                 AdjustDown(a, end, 0);
13.                 --end;
14.         }
15. }

复制代码

 

 假如我们想实现升序，将向下调解算法按照大堆的规则改一下就行 
向下调解算法和向上调解算法的空间复杂度都是（logN） 
堆排序中，建堆的时间复杂度是o（N），排序的时间复杂度是（N*logN）所以堆排序的总时间复杂度是N*logN
5.2 TOP-K问题

Top-k问题：即求数据中前k个最大的元素或者是最小的元素，一般情况下的数据量都比力大！
比如：专业前10名、世界五百强、富豪榜前十
堆排序可以或许资助我们在大量数据中筛选出最好的几个。
5.2.1 思绪

        比如说我们要从1000个学生的成绩中找到前10个分数最高的，方法就是将所有的数据放在一个数组里，直接建大堆，然后pop9次就可以找到了（pop中的向下调解算法可以使得每次pop出去的都是最大值，然后pop9次的缘故原由是因为第10次就可以直接去获取堆顶元素即可）

但是有些情况，上述思绪办理不了，分析：

5.2.2 通过数组验证TOP-K

1. void PrintTopK(int* a, int n, int k)
2. {
3.         //建前k个建小堆
4.         for (int i = (k - 1 - 1) / 2; i >= 0; i--)
5.                 AdjustDown(a, k, i);
6.         //将剩余n个数据不断与堆顶元素比较，大就交换,然后向下调整
7.         for (int i = k; i < n; i++)
8.         {
9.                 if (a[i] > a[0])
10.                 {
11.                         a[0] = a[i];//直接覆盖就行，不用交换
12.                         AdjustDown(a, k, 0);
13.                 }
14.         }
15.         //打印
16.         for(int i=0;i<k;i++)
17.         printf("%d ", a[i]);
18. }
20. void TestTopk()
21. {
22.         int n = 10000;
23.         int* a = (int*)malloc(sizeof(int) * n);
24.         srand((unsigned int)time(NULL));
25.         for (size_t i = 0; i < n; ++i)
26.         {
27.                 a[i] = rand() % 1000000;//随机数范围0-999999
28.         }
29. // 为了能够方便找到这些数
30.         a[5] = 1000000 + 1;
31.         a[1231] = 1000000 + 2;
32.         a[531] = 1000000 + 3;
33.         a[5121] = 1000000 + 4;
34.         a[115] = 1000000 + 5;
35.         a[2335] = 1000000 + 6;
36.         a[9999] = 1000000 + 7;
37.         a[76] = 1000000 + 8;
38.         a[423] = 1000000 + 9;
39.         a[3144] = 1000000 + 10;
40.         PrintTopK(a, n, 10);
41. }
43. int main()
44. {
45.         TestTopk();
46.         return 0;
47. }

复制代码

5.2.3 通过文件验证TOP-K

实在用数组的方法，并不能有效地模仿，我们可以尝试用文件的方式来验证

1. void CreateNDate()
2. {
3.         // 造数据
4.         int n = 10000;
5.         srand((unsigned int)time(NULL));
6.         const char* file = "data.txt";
7.         FILE* fin = fopen(file, "w");
8.         if (fin == NULL)
9.         {
10.                 perror("fopen error");
11.                 return;
12.         }
14.         for (size_t i = 0; i < n; ++i)
15.         {
16.                 int x = rand() % 1000000;
17.                 fprintf(fin, "%d\n", x);//将随机数写进文件
18.         }
19.         fclose(fin);
20. }
22. void PrintTopK(int k)
23. {
24.         const char* file = "data.txt";
25.         FILE* fout = fopen(file, "r");
26.         if (fout == NULL)
27.         {
28.                 perror("fopen fail");
29.                 return;
30.         }
32.         int* kminheap = (int*)malloc(sizeof(int) * k);
33.         if (kminheap == NULL)
34.         {
35.                 perror("malloc fail");
36.                 return;
37.         }
39.         for (int i = 0; i < k; i++)
40.         {
41.                 fscanf(fout, "%d", &kminheap[i]);//从文件读取数据
42.         }
44.         // 建小堆
45.         for (int i = (k - 1 - 1) / 2; i >= 0; i--)
46.         {
47.                 AdjustDown(kminheap, k, i);
48.         }
50.         int val = 0;
51.         while (!feof(fout))//feof是文件结束的标识，如果返回1，则说明文件结束
52.         {
53.                 fscanf(fout, "%d", &val);//fscaf的光标闪动到原先的位置，所以会从k的位置开始读
54.                 if (val > kminheap[0])
55.                 {
56.                         kminheap[0] = val;
57.                         AdjustDown(kminheap, k, 0);
58.                 }
59.         }
61.         for (int i = 0; i < k; i++)
62.         {
63.                 printf("%d ", kminheap[i]);
64.         }
65.         printf("\n");
66. }
67. int main()//该方法实现堆的顺序打印
68. {
69.         CreateNDate();
70.         PrintTopK(5);
71.         return 0;
72. }

复制代码

友友们上述代码有不明白的，看看博主关于文件操作里的函数介绍：
C语言：文件操作详解-CSDN博客

 不太好找，所以我们可以先解释创造数据的文件，然后再文件中修该出5个最大数，然后再实行一次函数

以上就是通过数组验证top和利用文件验证tok的方法！！

 

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