实现二叉树_堆

一. 堆的实现

在上一节中我们知道了堆的数据布局，实在就是一种特殊的完全二叉树，堆的底层数据布局就是数组，以是我们就可以界说堆的布局：

1. //定义堆的结构--数组
2. typedef int HPDataType;
3. typedef struct Heap
4. {
5.         HPDataType* arr;
6.         int size;//有效的数据个数
7.         int capacity;//空间大小
8. }HP;
10. void HPinit(HP* php);//堆的初始化
11. void HPdistroy(HP* php);//堆的销毁
12. void HPPush(HP* php, HPDataType x);//向堆中插入数据
13. void AdjustUP(HPDataType* arr, int child);//堆的向上调整法
14. void Swap(HPDataType* x, HPDataType* y);//数据交换
15. void HPpop(HP* php);//删除数据
16. void AdjustDown(HPDataType* arr, int parent, int n);//堆的向下调整算法
17. HPDataType HPTop(HP* php);//取堆顶数据

复制代码

下面是详细的算法实现：

1. void HPinit(HP* php)//堆的初始化
2. {
3.         assert(php);
4.         php->arr = NULL;
5.         php->size = php->capacity = 0;
6. }
8. void HPdistroy(HP* php)//堆的销毁
9. {
10.         if (php->arr)
11.                 free(php->arr);
12.         php->arr = NULL;
13.         php->size = php->capacity = 0;
14. }
16. void Swap(HPDataType* x, HPDataType* y)//数据交换
17. {
18.         HPDataType tmp = *x;
19.         *x = *y;
20.         *y = tmp;
21. }
23. void AdjustUP(HPDataType* arr, int child)//堆的向上调整法
24. {
25.         int parent = (child - 1) / 2;
26.         while (child >= 0)
27.         {
28.                 if (arr[child] < arr[parent])
29.                 {
30.                         Swap(&arr[parent], &arr[child]);
31.                         child = parent;
32.                         parent = (child - 1) / 2;
33.                 }
34.                 else
35.                 {
36.                         break;
37.                 }
38.         }
39.        
40. }
42. void HPPush(HP* php, HPDataType x) //堆的插入
43. {
44.         assert(php);
45.         //判断空间是否足够
46.         if (php->size == php->capacity)
47.         {
48.                 //扩容
49.                 {
50.                         int newCapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
51.                         HPDataType* tmp = realloc(php->arr, newCapacity * sizeof(HPDataType));
52.                         if (tmp == NULL)
53.                         {
54.                                 printf("realloc fail!");
55.                                 exit(1);
56.                         }
57.                         php->arr = tmp;
58.                         php->capacity = newCapacity;
59.                 }
60.         }
61.         php->arr[php->size] = x;
62.         //进行堆的调整 （完成我们的大堆或者小堆）
63.         AdjustUP(php->arr, php->size);
64.         ++php->size;
65. }
67. //堆的向下调整算法
68. void AdjustDown(HPDataType* arr, int parent, int n)
69. {
70.         int child = parent * 2 + 1;//左孩子
71.         while (child<n)
72.         {
73.                 //找到左右孩子中的最小值
74.                 if (child + 1 < n && arr[child] > arr[child + 1])
75.                 {
76.                         child++;
77.                 }
78.                 if (arr[child] < arr[parent])
79.                 {
80.                         Swap(&arr[child], &arr[parent]);
81.                         parent = child;
82.                         child = parent * 2 + 1;
83.                 }
84.                 else
85.                 {
86.                         break;
87.                 }
88.         }
89. }
91. //在堆中删除数据是删除堆顶的数据，所以在我们删除完一个数据之后还要保持这个堆的结构是原本的小堆或者大堆，还要进行数据调整
92. void HPpop(HP* php)//删除数据
93. {
94.         assert(php && php->size);
95.         //arr[0]   arr[size-1]
96.         Swap(&php->arr[0], &php->arr[php->size - 1]);
97.         //向下调整算法
98.         AdjustDown(php->arr, 0, php->size);
99.         --php->size;
100. }
101. //判空
102. bool HPEmpty(HP* php)
103. {
104.         assert(php);
105.         return php->size == 0;
106. }
108. HPDataType HPTop(HP* php)//取堆顶数据
109. {
110.         assert(php && php->size);
111.         return php->arr[0];
112. }

复制代码

 上面就是对于堆这样一个数据布局中数据的插入、删除、以及如何完成我们想要的大堆照旧小堆等，通过算法一一实现。
二. 向上调整算法

我们在上面的算法中可能会看到一个向上调整算法，这是一个比较紧张的算法，用于完成我们想要的数据布局。如何来理解呢?首先我们就拿小堆来举例子，如果我们现在要完成一个小堆的数据布局，我们首先要往一个数组中插入数据：

以是第一步，我们来插入数据，先判断空间是否足够，如果不敷的话就扩容，末了再往数组中插入数据，这是比较最根本的步调，然后再来实现我们要的小堆，这里就必要我们的AdjustUP向上调整算法：

 根据上面的图片我们来做对代码的解释，如图所示，我们就拿17 20 10 13 19 15 这几个数字来完成我们的小堆，我们在AdjustUP函数中传入（php->arr, php->size），实在就是指数组，以及传入的末了一个数据，以是当我们传入了两个数据之后，我们就要开始比较了，20是孩子结点，通过计算找到父亲结点，然后比较二者的巨细，因为我们这次要完成的是小堆，以是此时两者不消交换，但是当在传入数据10的时候，通过计算发现10<17，要交换。但是如果还继续传入数据的话，我们就要一步步继续向上比较，以是此时我们要让child即是来的parent，parent继续即是（child-1）/2，继续向上比较，直到child小于0，以是我们的while循环条件是（child>=0)，我们来调试一下判断我们的代码是否正确：

 由此看出来我们确实实现了小堆的操作，大家可以自己操作实现一下。
三. 向下调整算法

堆的删除的删除堆顶的数据，但是如果直接删除堆顶的数据之后，我们本来的大堆大概小堆的顺序就会改变，可能发生顺序的紊乱，以是如果我们要删除堆中的一个数据的话，也就是出堆，出的是堆顶的数据，我们一般采用的是交换堆顶数据和最末尾的数据：

像上图中的代码一样，先交换堆顶的数据和最末尾的数据，然后删除末尾的数据，也就是把堆顶数据出堆，但是出堆之后的堆并不一定是小堆了，以是我们现在要进行向下调整算法，

1. void AdjustDown(HPDataType* arr, int parent, int n)
2. {
3.         int child = parent * 2 + 1;//左孩子
4.         while (child<n)
5.         {
6.                 //找到左右孩子中的最小值
7.                 if (child + 1 < n && arr[child] > arr[child + 1])
8.                 {
9.                         child++;
10.                 }
11.                 if (arr[child] < arr[parent])
12.                 {
13.                         Swap(&arr[child], &arr[parent]);
14.                         parent = child;
15.                         child = parent * 2 + 1;
16.                 }
17.                 else
18.                 {
19.                         break;
20.                 }
21.         }
22. }

复制代码

 

取堆顶数据 ：

1. //判空
2. bool HPEmpty(HP* php)
3. {
4.         assert(php);
5.         return php->size == 0;
6. }
8. HPDataType HPTop(HP* php)//取堆顶数据
9. {
10.         assert(php && php->size);
11.         return php->arr[0];
12. }

复制代码

 
四. 堆的应用

那么堆有哪些应用呢？可以用来排序，堆排序。在前面我们学习过对于数据的一些排序方法，好比冒泡排序等，那么如何利用堆来进行排序，并且使空间复杂度为O(1)呢？

1. //堆排序   不额外开辟空间
2. void HeapSort(int* arr, int n)
3. {
4.         //建堆
5.         //升序----大堆
6.         //降序----小堆
7.         for (int i = 0; i < n; i++)
8.         {
9.                 AdjustUP(arr,i);
10.         }
11.         //循环的将堆顶数据与最后位置数据进行交换
12.         int end = n - 1;
13.         while (end>0)
14.         {
15.                 Swap(&arr[0], &arr[end]);
16.                 AdjustDown(arr, 0, end);
17.                 end--;
18.         }
19. }
20. int main()
21. {
22.         //test01();
23.         //给定一个数据，随数组中的数据进行排序
24.         int arr[] = { 17,20,10,13,19,15 };
25.         HeapSort(arr, 6);
26.         for (int i = 0; i < 6; i++)
27.         {
28.                 printf("%d ", arr[i]);
29.         }
30.         printf("\n");
31.         return 0;
32. }

复制代码

上面就将数组进行了降序分列，那么思路是怎样的呢？

 上图也赋上了详细的堆排序思路供大家参考，希望大家可以汲取到有用的知识！

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