【数据结构】堆-C语言版（三）-阿里云开发者社区

堆的实现：

045-heap.h

1. #pragma once
2. #include<stdio.h>
3. #include<stdlib.h>
4. #include<string.h>
5. #include<stdbool.h>
6. #include<assert.h>
7. 
8. 
9. typedef int HPDataType;
10. struct Heap
11. {
12.   HPDataType* a;
13.   int size;
14.   int capacity;
15. };
16. 
17. typedef struct Heap HP;
18. 
19. //交换
20. void Swap(int* p1, int* p2);
21. 
22. //向下调整
23. void AdjustDown(int* a, int n, int parent);
24. 
25. //向上调整
26. void AdjustUp(int* a, int child);
27. 
28. //初始化
29. void HeapInit(HP* php, HPDataType* a, int n);
30. 
31. //销毁
32. void HeapDestroy(HP* php);
33. 
34. //堆的插入
35. void HeapPush(HP* php, HPDataType x);
36. 
37. //堆的删除
38. void HeapPop(HP* php);
39. 
40. //返回堆顶元素
41. HPDataType HeapTop(HP* php);
42. 
43. //堆的大小
44. int HeapSize(HP* php);
45. 
46. //判空
47. bool HeapEmpty(HP* php);
48. 
49. //打印
50. void HeapPrint(HP* php);

1. #define  _CRT_SECURE_NO_WARNINGS  1
2. #include "045-Heap.h"
3. 
4. //打印
5. void HeapPrint(HP* php)
6. {
7.  for (int i = 0; i < php->size; i++)
8.  {
9.    printf("%d ", php->a[i]);
10.   }
11.   printf("\n");
12. 
13.   int num = 0;
14.   int levelSize = 1;
15.   for (int i = 0; i < php->size; i++)
16.   {
17.     printf("%d ", php->a[i]);
18.     num++;
19.     if (num == levelSize)
20.     {
21.       printf("\n");
22.       levelSize *= 2;
23.       num = 0;
24. 
25.     }
26. 
27.   }
28. 
29.   printf("\n\n");
30. }
31. 
32. //交换
33. void Swap(int* p1, int* p2)
34. {
35.   int tmp = *p1;
36.   *p1 = *p2;
37.   *p2 = tmp;
38. }
39. 
40. //向下调整
41. void AdjustDown(int* a, int n, int parent)
42. {
43.   int child = parent * 2 + 1;
44.   while (child < n)
45.   {
46.     //选出左右孩子中的小孩子，建大堆就把第二个<改成>
47.     if (child + 1 < n && a[child + 1] < a[child])
48.     {
49.       child++;
50.     }
51.     //小孩子比父亲小，交换小孩子和父亲，建大堆就把<改成>
52.     if (a[child] < a[parent])
53.     {
54.       Swap(&a[child], &a[parent]);
55.       //交换父亲和孩子后，可能导致不满足堆的定义，需要继续调整
56.       parent = child;
57.       child = parent * 2 + 1;
58.     }
59.     //小孩子比父亲大，跳出while循环，结束这一次的向下调整，否则一直死循环并且什么都不做
60.     else
61.     {
62.       break;
63.     }
64.   }
65. }
66. 
67. //向上调整
68. void AdjustUp(int* a, int child)
69. {
70.   int parent = (child - 1) / 2;
71.   while (child > 0)
72.   {
73.     if (a[child] > a[parent])
74.     {
75.       Swap(&a[child], &a[parent]);
76.       child = parent;
77.       parent = (child - 1) / 2;
78.     }
79.     else
80.     {
81.       break;
82.     }
83.   }
84. }
85. 
86. //初始化
87. void HeapInit(HP* php, HPDataType* a, int n)
88. {
89.   assert(php);
90.   php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
91.   if (php->a == NULL)
92.   {
93.     printf("malloc fail\n");
94.     exit(-1);
95.   }
96. 
97.   memcpy(php->a, a, sizeof(HPDataType) * n);
98.   php->size = n;
99.   php->capacity = n;
100. 
101.  //建堆
102.  for (int i = (n - 1 - 1) / 2; i >= 0; i--)
103.  {
104.    AdjustDown(php->a, php->size, i);
105.  }
106. }
107. 
108. //销毁
109. void HeapDestroy(HP* php)
110. {
111.  assert(php);
112.  free(php->a);
113.  php->a = NULL;
114.  php->size = 0;
115.  php->capacity = 0;
116. }
117. 
118. //堆的插入
119. void HeapPush(HP* php, HPDataType x)
120. {
121.  assert(php);
122. 
123.  //满了则需要增容
124.  if (php->size == php->capacity)
125.  {
126.    HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * 2 * php->capacity);
127.    if (tmp == NULL)
128.    {
129.      printf("realloc fail\n");
130.      exit(-1);
131.    }
132.    php->a = tmp;
133.    php->capacity *= 2;
134.  }
135. 
136.  php->a[php->size] = x;
137.  php->size++;
138. 
139.  AdjustUp(php->a, php->size - 1);
140. }
141. 
142. //堆的删除
143. void HeapPop(HP* php)
144. {
145.  assert(php);
146.  assert(php->size > 0);
147. 
148.  //将堆顶元素和最后一个叶子结点进行交换
149.  Swap(&php->a[0], &php->a[php->size - 1]);
150.  php->size--;
151. 
152.  //对堆顶元素进行向下调整
153.  AdjustDown(php->a, php->size, 0);
154. 
155. }
156. 
157. //返回堆顶元素
158. HPDataType HeapTop(HP* php)
159. {
160.  assert(php);
161.  return php->a[0];
162. }
163. 
164. //堆的大小
165. int HeapSize(HP* php)
166. {
167.  assert(php);
168.  return php->size;
169. }
170. 
171. //堆判空
172. bool HeapEmpty(HP* php)
173. {
174.  assert(php);
175.  return php->size == 0;
176. }

045-test.c

1. #define  _CRT_SECURE_NO_WARNINGS  1
2. #include "045-Heap.h"
3. 
4. int main()
5. {
6.  int a1[] = { 15,18,28,34,65,19,49,25,37,27 };
7.  int n = sizeof(a1) / sizeof(a1[0]);
8. 
9.  HP hp;
10.   HeapInit(&hp, a1, n);
11.   HeapPrint(&hp);
12. 
13.   HeapPush(&hp, 8);
14.   HeapPrint(&hp);
15. 
16.   HeapPush(&hp, 88);
17.   HeapPrint(&hp);
18. 
19.   HeapDestroy(&hp);
20. 
21.   return 0;
22. }

运行结果如下图所示：

TOP k问题

TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。

比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。

对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：

（1）用数据集合中前K个元素来建堆

求前k个最大的元素，则把前k个数建小堆

求前k个最小的元素，则把前k个数建大堆

（2）用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素

如果建了小堆，剩下N-K个元素和堆顶元素比较，若比堆顶元素大，则替换堆顶元素，调堆如果建了大堆，剩下N-K个元素和堆顶元素比较，若比堆顶元素小，则替换堆顶元素，调堆

将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。

总结：

建堆：向下调整算法

堆的删除：向下调整

堆的插入：向上调整

堆的应用

最小的k个数 OJ链接

思路一：将堆的实现的代码拷贝过来，建小堆，将前k个元素保存到一个数组中输出

1. typedef int HPDataType;
2. struct Heap
3. {
4.  HPDataType* a;
5.  int size;
6.  int capacity;
7. };
8. 
9. typedef struct Heap HP;
10. 
11. //交换
12. void Swap(int* p1, int* p2);
13. 
14. //向下调整
15. void AdjustDown(int* a, int n, int parent);
16. 
17. //向上调整
18. void AdjustUp(int* a, int child);
19. 
20. //初始化
21. void HeapInit(HP* php, HPDataType* a, int n);
22. 
23. //销毁
24. void HeapDestroy(HP* php);
25. 
26. //堆的插入
27. void HeapPush(HP* php, HPDataType x);
28. 
29. //堆的删除
30. void HeapPop(HP* php);
31. 
32. //返回堆顶元素
33. HPDataType HeapTop(HP* php);
34. 
35. //堆的大小
36. int HeapSize(HP* php);
37. 
38. //判空
39. bool HeapEmpty(HP* php);
40. 
41. //打印
42. void HeapPrint(HP* php);
43. 
44. //打印
45. void HeapPrint(HP* php)
46. {
47.   for (int i = 0; i < php->size; i++)
48.   {
49.     printf("%d ", php->a[i]);
50.   }
51.   printf("\n");
52. 
53.   int num = 0;
54.   int levelSize = 1;
55.   for (int i = 0; i < php->size; i++)
56.   {
57.     printf("%d ", php->a[i]);
58.     num++;
59.     if (num == levelSize)
60.     {
61.       printf("\n");
62.       levelSize *= 2;
63.       num = 0;
64. 
65.     }
66. 
67.   }
68. 
69.   printf("\n\n");
70. }
71. 
72. //交换
73. void Swap(int* p1, int* p2)
74. {
75.   int tmp = *p1;
76.   *p1 = *p2;
77.   *p2 = tmp;
78. }
79. 
80. //向下调整
81. void AdjustDown(int* a, int n, int parent)
82. {
83.   int child = parent * 2 + 1;
84.   while (child < n)
85.   {
86.     //选出左右孩子中的小孩子，建大堆就把第二个<改成>
87.     if (child + 1 < n && a[child + 1] < a[child])
88.     {
89.       child++;
90.     }
91.     //小孩子比父亲小，交换小孩子和父亲，建大堆就把<改成>
92.     if (a[child] < a[parent])
93.     {
94.       Swap(&a[child], &a[parent]);
95.       //交换父亲和孩子后，可能导致不满足堆的定义，需要继续调整
96.       parent = child;
97.       child = parent * 2 + 1;
98.     }
99.     //小孩子比父亲大，跳出while循环，结束这一次的向下调整，否则一直死循环并且什么都不做
100.    else
101.    {
102.      break;
103.    }
104.  }
105. }
106. 
107. //向上调整
108. void AdjustUp(int* a, int child)
109. {
110.  int parent = (child - 1) / 2;
111.  while (child > 0)
112.  {
113.    if (a[child] > a[parent])
114.    {
115.      Swap(&a[child], &a[parent]);
116.      child = parent;
117.      parent = (child - 1) / 2;
118.    }
119.    else
120.    {
121.      break;
122.    }
123.  }
124. }
125. 
126. //初始化
127. void HeapInit(HP* php, HPDataType* a, int n)
128. {
129.  assert(php);
130.  php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
131.  if (php->a == NULL)
132.  {
133.    printf("malloc fail\n");
134.    exit(-1);
135.  }
136. 
137.  memcpy(php->a, a, sizeof(HPDataType) * n);
138.  php->size = n;
139.  php->capacity = n;
140. 
141.  //建堆
142.  for (int i = (n - 1 - 1) / 2; i >= 0; i--)
143.  {
144.    AdjustDown(php->a, php->size, i);
145.  }
146. }
147. 
148. //销毁
149. void HeapDestroy(HP* php)
150. {
151.  assert(php);
152.  free(php->a);
153.  php->a = NULL;
154.  php->size = 0;
155.  php->capacity = 0;
156. }
157. 
158. //堆的插入
159. void HeapPush(HP* php, HPDataType x)
160. {
161.  assert(php);
162. 
163.  //满了则需要增容
164.  if (php->size == php->capacity)
165.  {
166.    HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * 2 * php->capacity);
167.    if (tmp == NULL)
168.    {
169.      printf("realloc fail\n");
170.      exit(-1);
171.    }
172.    php->a = tmp;
173.    php->capacity *= 2;
174.  }
175. 
176.  php->a[php->size] = x;
177.  php->size++;
178. 
179.  AdjustUp(php->a, php->size - 1);
180. }
181. 
182. //堆的删除
183. void HeapPop(HP* php)
184. {
185.  assert(php);
186.  assert(php->size > 0);
187. 
188.  //将堆顶元素和最后一个叶子结点进行交换
189.  Swap(&php->a[0], &php->a[php->size - 1]);
190.  php->size--;
191. 
192.  //对堆顶元素进行向下调整
193.  AdjustDown(php->a, php->size, 0);
194. 
195. }
196. 
197. //返回堆顶元素
198. HPDataType HeapTop(HP* php)
199. {
200.  assert(php);
201.  return php->a[0];
202. }
203. 
204. //堆的大小
205. int HeapSize(HP* php)
206. {
207.  assert(php);
208.  return php->size;
209. }
210. 
211. //堆判空
212. bool HeapEmpty(HP* php)
213. {
214.  assert(php);
215.  return php->size == 0;
216. }
217. 
218. int* getLeastNumbers(int* arr, int arrSize, int k, int* returnSize){
219.     HP hp;
220.     HeapInit(&hp,arr,arrSize);
221. 
222.     int *retArr = (int*)malloc(sizeof(int)*k);
223.     for(int i = 0;i<k;i++)
224.     {
225.         retArr[i] = HeapTop(&hp);
226.         HeapPop(&hp);
227.     }
228. 
229.     HeapDestroy(&hp);
230.     *returnSize = k;
231.     return retArr;
232. }

思路二：求最小的k个数，即Top k问题，用前k个元素建大堆，用剩余的N-k个元素依次和堆顶元素比较，如果比堆顶元素小，则将该元素和堆顶元素进行交换，调堆。最后堆里的元素就是最小的k个数

1. //交换
2. void Swap(int* p1, int* p2)
3. {
4.    int tmp = *p1;
5.    *p1 = *p2;
6.    *p2 = tmp;
7. }
8. 
9. //向下调整
10. void AdjustDown(int* a, int n, int parent)
11. {
12.   int child = parent * 2 + 1;
13.   while (child < n)
14.     {
15.     //选出左右孩子中的小孩子，建大堆就把第二个<改成>
16.     if (child + 1 < n && a[child + 1] > a[child])
17.     {
18.       child++;
19.     }
20.     //小孩子比父亲小，交换小孩子和父亲，建大堆就把<改成>
21.     if (a[child] > a[parent])
22.     {
23.       Swap(&a[child], &a[parent]);
24.       //交换父亲和孩子后，可能导致不满足堆的定义，需要继续调整
25.       parent = child;
26.       child = parent * 2 + 1;
27.     }
28.     //小孩子比父亲大，跳出while循环，结束这一次的向下调整，否则一直死循环并且什么都不做
29.     else
30.     {
31.       break;
32.     }
33.   }
34. }
35. 
36. int* getLeastNumbers(int* arr, int arrSize, int k, int* returnSize){
37.     
38.     if(k == 0)
39.     {
40.         *returnSize = 0;
41.         return NULL;
42.     }
43.     int *retArr = (int*)malloc(sizeof(int)*k);
44.    
45.     //取出前k个数
46.     for(int i=0;i<k;i++)
47.     {
48.         retArr[i] = arr[i];
49.     }
50. 
51.     //对前k个数向下调整建大堆
52.     for(int j = (k-1-1)/2;j>=0;j--)
53.     {
54.         AdjustDown(retArr,k,j);
55.     }
56. 
57.     //剩下的arrSize - k个数，如果比堆顶的元素小，就将该元素和堆顶元素进行交换,调堆
58.     for(int m =  k;m<arrSize;m++)
59.     {
60.         if(arr[m] < retArr[0])
61.         {
62.             retArr[0] = arr[m];
63.             AdjustDown(retArr,k,0);
64.         }
65.     }
66. 
67.     *returnSize = k;
68.     return retArr;
69. }

【数据结构】堆-C语言版（三）

堆的实现：

热门文章

最新文章

相关课程

相关电子书