二叉树——堆详解-阿里云开发者社区

前言：

之前我们已经学习过了二叉树的基本知识，接下来我们就要上些“硬菜”了，话不多说，开始我们今天的学习吧！

一、堆的结构

前文我们已经交待了什么为堆？以及堆的分类。我们既然已经对上文的基础知识已经明白，那么我们现在就来探讨以下如何实现一个堆。

我们想，数据在内存中的存放是不是连续的，不以人的意志为改变，对吧。堆，是一个完全二叉树，在内存的存放不存在中间为空的情况。所以，咱们可以以数组的方式来存储堆。以下，是堆的结构：

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

看起来和我们之前的顺序表结构有些类似。虽然，我们知道了其结构，但是我们不知道如何存储呀！要是随便存储，那和普通数组，普通二叉树有何区别。为了能够实现堆，我们将采取以下的方法。

二、向上调整和向下调整

2.1 向上调整

什么是向上调整呢？对于一个二叉树，我们知道了孩子节点，我们是不是可以反推出父节点。经行比较，小的成为父亲（建小堆），大的成为孩子，这样进行一一比较，小堆是不是就建好了。

向上调整就是：谁小谁当爹，谁大谁儿子，就这么简单。代码实现如下：

1. void AdjustUp(HPDataType* a, int child)
2. {
3.  int parent = (child - 1) / 2;
4.  while (child > 0)
5.  {
6.    if (a[parent] > a[child])
7.    {
8.      sweap(&a[parent], &a[child]);//注意：这里一定要传地址，&不要忘记
9.      child = parent;
10.       parent = (child - 1) / 2;
11.     }
12.     else
13.     {
14.       break;
15.     }
16.   }
17. }

相信大家的sweap函数都能够独立实现，这里就不在展示，要是无法实现可参考文末处代码。

2.2 向下调整

向下调整是基于一个建好的堆来经行实现的，为啥？向上调整从子节点调，那向下调整是不是应该从父节点开始调。要是这个堆一会是大堆，一会是小堆，那还能调吗？肯定是不行了呀。所以：向下调整健堆的前提是：左右子树必须是一个堆，才能调整。

其实现思路和向上调整类似，这里直接来看代码：

1. void AdjustDown(HPDataType* a, int n, int parent)
2. {
3.  int child = parent * 2 + 1;
4.  while (child < n)
5.  {
6.    if (a[child] > a[child+1])//此步的目的是找到最小的
7.    {
8.      child++;
9.    }
10.     if (a[parent] > a[child])
11.     {
12.       sweap(&a[parent], &a[child]);
13.       parent = child;
14.       child = parent * 2 + 1;
15.     }
16.     else
17.     {
18.       break;
19.     }
20.   }
21. }

有了向上调整，对于向下调整大家应该可以理解。

2.3 向上调整和向下调整时间复杂度比较

我们说了这么多肯定要考虑其效率问题，我们对于时间复杂度的关注度是一如既往的深。大家会有这样的感觉：这两个时间复杂度应该一样吧，都是O（N*logN）。大家先别急，我给大家推一遍就明白了：

它们的时间复杂度为什么会有差别呢？很简单，向下调整建堆是用小成大，大乘小。向上调整建堆是用小乘小，大乘大。所以会有这样的差距。从效率上看，向下调整建堆的效率大于向上调整建堆。在后文推排序中所用的方法为：向下调整。

三、堆的实现

既然我们的方法都已具备，那我们现在就拿下堆吧！

3.1 堆的初始化

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

3.2 堆的销毁

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

3.3 堆的插入

1. void sweap(int* p1, int* p2)
2. {
3.  int tmp = *p1;
4.  *p1 = *p2;
5.  *p2 = tmp;
6. }
7. void AdjustUp(HPDataType* a, int child)
8. {
9.  int parent = (child - 1) / 2;
10.   while (child > 0)
11.   {
12.     if (a[parent] > a[child])
13.     {
14.       sweap(&a[parent], &a[child]);//注意：这里一定要传地址，&不要忘记
15.       child = parent;
16.       parent = (child - 1) / 2;
17.     }
18.     else
19.     {
20.       break;
21.     }
22.   }
23. }
24. void HeapPush(Heap* hp, HPDataType x)
25. {
26.   assert(hp);
27.   if (hp->capacity == hp->size)
28.   {
29.     int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
30.     HPDataType* newnode = (HPDataType*)realloc(hp->a,newcapacity * sizeof(HPDataType));
31.     if (hp->a == NULL)
32.     {
33.       perror("realloc fail");
34.       return;
35.     }
36.     hp->a = newnode;
37.     hp->capacity = newcapacity;
38.   }
39.   hp->a[hp->size] = x;
40.   hp->size++;
41.   //也可写成：hp->a[hp->size++] = x;
42.   AdjustUp(hp->a, hp->size - 1);//向上调整
43. }

3.4堆的删除

1. void AdjustDown(HPDataType* a, int n, int parent)
2. {
3.  int child = parent * 2 + 1;
4.  while (child < n)
5.  {
6.    if (a[child] > a[child+1])//此步的目的是找到最小的
7.    {
8.      child++;
9.    }
10.     if (a[parent] > a[child])
11.     {
12.       sweap(&a[parent], &a[child]);
13.       parent = child;
14.       child = parent * 2 + 1;
15.     }
16.     else
17.     {
18.       break;
19.     }
20.   }
21. }
22. void HeapPop(Heap* hp)
23. {
24.   assert(hp);
25.   assert(hp->size > 0);
26.   sweap(&hp->a[0], &hp->a[hp->size - 1]);//删除顶元素
27.   hp->size--;
28.   AdjustDown(hp->a, hp->size, 0);//向下调整
29. }

堆的删除不是删除最后一个元素，而是删除首元素！！！

3.5 取堆顶元素

1. HPDataType HeapTop(Heap* hp)
2. {
3.  assert(hp);
4.  assert(hp->size > 0);
5.  return hp->a[0];
6. }

3.6 对堆判空

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

好了，以上便是对堆的全部实现，大家稍微休息片刻，接下来咱们进入堆排序。

四、堆排序

接下来，咱们来搞堆排序。对于堆排序，大家有没有什么想法：升序是建大堆还是小堆，降序是建小堆还是大堆。对于这个问题，有人肯定会有这样的想法：降序，那不是非大堆莫属，升序，那不是非小堆莫属。非也。

那么，有什么方法呢？答案为：降序：小堆；升序：大堆。

就以降序为例：排降序咱们首先先把根（也就是祖先）扔到最后，之后不在理会它，推选出下一个祖先，重复即可。

以上，便为实现思路。

这只是一个大致方向，我们拿这个大致方向去实现肯定会困难重重。那我们面临最大的困难是什么呢？答案为：向下调整的使用条件。向下调整使用的前提是什么？左右子树必须是一个堆，才能调整。这个问题说起来不容易，实际做起来也不容易。那么，我们该如何完成呢？如下：

1.我们想找到最后一个节点的父节点。

2.将这个小堆进行向下调整。

3.然后，对其它节点也使用其类似方法。

这个方法是不是特别巧妙，以“农村包围城市”的思想，悄无声息就完成了这件大事。妙哉！

接下来便是推排序代码实现：

1. void HeapSort(int* a, int n)
2. {
3.  for (int i = (n - 1 - 1) / 2; i >= 0; i--)
4.  {
5.    AdjustDown(a, n, i);//见小堆
6.  }
7.  int end = n - 1;
8.  while (end)
9.  {
10.     sweap(&a[0], &a[end]);
11.     AdjustDown(a, end, 0);//经行排序
12.     end--;
13.   }
14. }

五、TOP-K 问题

什么为TOP-K问题呢？以下为大家构建一个场景：

你在大学里苦学两年，计划在大二的暑假的暑假找一份实习。和你预期一样，一家公司向你发起了面试，对于前面的计算机知识你对答入流，当你以为你能够“黄袍加身”之时，面试官问出了最后一题，我给你一个文件，里面有十万个数据，给我选出最大的十个出来。你当时在心里想：就这。你立马动态开辟了这么大的空间，运用堆排序，立马拿到了结果。面试官喝了口茶，说了句：“太大了。”你以为说的是茶太烫了，想着要不要做点什么的时候，然后面试官缓缓地说：“如果我给你1MB的空间，能不能搞出来，1KB的空间，行不行？”你不由得在心中想：你就是想为难我，当没想到，我重生了（一键三连即可听故事），这个问题早已被我攻克，我可是要站在顶尖的人。于是，你大笔一挥写出的代码震惊到面试官，于是如愿成为实习生。

本问题已经明确，在很大的数据面前，用极小的内存得到想要的结果。

具体实现思路如下：在十万数据中得到最大的十个数。我们可先取出十个数，建小堆，和其他数字比，如果有数字比顶元素大，便替换掉顶元素，进入堆，在向下调整，直到对比完。

代码实现如下：

1. void CreateNDate()
2. {
3.  // 造数据
4.  int n = 10000;
5.  srand(time(0));
6.  const char* file = "data.txt";
7.  FILE* fin = fopen(file, "w");
8.  if (fin == NULL)
9.  {
10.     perror("fopen error");
11.     return;
12.   }
13. 
14.   for (size_t i = 0; i < n; ++i)
15.   {
16.     int x = rand() % 1000000;
17.     fprintf(fin, "%d\n", x);
18.   }
19. 
20.   fclose(fin);
21. }
22. 
23. void PrintTopK(int k)
24. {
25.   int k;
26.   printf("请输入k>:");
27.   scanf("%d", &k);
28.   int* kminheap = (int*)malloc(sizeof(int) * k);
29.   if (kminheap == NULL)
30.   {
31.     perror("malloc fail");
32.     return;
33.   }
34.   const char* file = "data.txt";
35.   FILE* fout = fopen(file, "r");
36.   if (fout == NULL)
37.   {
38.     perror("fopen error");
39.     return;
40.   }
41. 
42.   // 读取文件中前k个数
43.   for (int i = 0; i < k; i++)
44.   {
45.     fscanf(fout, "%d", &kminheap[i]);
46.   }
47.   // 建K个数的小堆
48.   for (int i = (k - 1 - 1) / 2; i >= 0; i--)
49.   {
50.     AdjustDown(kminheap, k, i);
51.   }
52. 
53.   // 读取剩下的N-K个数
54.   int x = 0;
55.   while (fscanf(fout, "%d", &x) > 0)
56.   {
57.     if (x > kminheap[0])
58.     {
59.       kminheap[0] = x;
60.       AdjustDown(kminheap, k, 0);
61.     }
62.   }
63. 
64.   printf("最大前%d个数：", k);
65.   for (int i = 0; i < k; i++)
66.   {
67.     printf("%d ", kminheap[i]);
68.   }
69.   printf("\n");
70. }

六、代码总览

heap.h

1. #pragma once
2. #include<stdio.h>
3. #include<stdlib.h>
4. #include<stdbool.h>
5. #include<assert.h>
6. 
7. typedef int HPDataType;
8. typedef struct Heap
9. {
10.   HPDataType* a;
11.   int size;
12.   int capacity;
13. }Heap;
14. 
15. void HeapInit(Heap* php);
16. // 堆的销毁
17. void HeapDestory(Heap* hp);
18. // 堆的插入
19. void HeapPush(Heap* hp, HPDataType x);
20. // 堆的删除
21. void HeapPop(Heap* hp);
22. // 取堆顶的数据
23. HPDataType HeapTop(Heap* hp);
24. // 堆的数据个数
25. int HeapSize(Heap* hp);
26. // 堆的判空
27. bool HeapEmpty(Heap* hp);
28. //向下调整建堆
29. void AdjustDown(HPDataType* a, int n, int parent);
30. void sweap(int* p1, int* p2);

heap.c

1. #include"heap.h"
2. 
3. void HeapInit(Heap* php)
4. {
5.  assert(php);
6.  php->a = NULL;
7.  php->capacity = php->size = 0;
8. }
9. // 堆的销毁
10. void HeapDestory(Heap* hp)
11. {
12.   assert(hp);
13.   free(hp->a);
14.   hp->a = NULL;
15.   hp->capacity = hp->size = 0;
16. }
17. // 堆的插入
18. void sweap(int* p1, int* p2)
19. {
20.   int tmp = *p1;
21.   *p1 = *p2;
22.   *p2 = tmp;
23. }
24. void AdjustUp(HPDataType* a, int child)
25. {
26.   int parent = (child - 1) / 2;
27.   while (child > 0)
28.   {
29.     if (a[parent] > a[child])
30.     {
31.       sweap(&a[parent], &a[child]);//注意：这里一定要传地址，&不要忘记
32.       child = parent;
33.       parent = (child - 1) / 2;
34.     }
35.     else
36.     {
37.       break;
38.     }
39.   }
40. }
41. void HeapPush(Heap* hp, HPDataType x)
42. {
43.   assert(hp);
44.   if (hp->capacity == hp->size)
45.   {
46.     int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
47.     HPDataType* newnode = (HPDataType*)realloc(hp->a,newcapacity * sizeof(HPDataType));
48.     if (hp->a == NULL)
49.     {
50.       perror("realloc fail");
51.       return;
52.     }
53.     hp->a = newnode;
54.     hp->capacity = newcapacity;
55.   }
56.   hp->a[hp->size] = x;
57.   hp->size++;
58.   //也可写成：hp->a[hp->size++] = x;
59.   AdjustUp(hp->a, hp->size - 1);//向上调整
60. }
61. // 堆的删除
62. void AdjustDown(HPDataType* a, int n, int parent)
63. {
64.   int child = parent * 2 + 1;
65.   while (child < n)
66.   {
67.     if (a[child] > a[child+1])//此步的目的是找到最小的
68.     {
69.       child++;
70.     }
71.     if (a[parent] > a[child])
72.     {
73.       sweap(&a[parent], &a[child]);
74.       parent = child;
75.       child = parent * 2 + 1;
76.     }
77.     else
78.     {
79.       break;
80.     }
81.   }
82. }
83. void HeapPop(Heap* hp)
84. {
85.   assert(hp);
86.   assert(hp->size > 0);
87.   sweap(&hp->a[0], &hp->a[hp->size - 1]);//删除顶元素
88.   hp->size--;
89.   AdjustDown(hp->a, hp->size, 0);//向下调整
90. }
91. // 取堆顶的数据
92. HPDataType HeapTop(Heap* hp)
93. {
94.   assert(hp);
95.   assert(hp->size > 0);
96.   return hp->a[0];
97. }
98. // 堆的数据个数
99. int HeapSize(Heap* hp)
100. {
101.  assert(hp);
102.  return hp->size;
103. }
104. // 堆的判空
105. bool HeapEmpty(Heap* hp)
106. {
107.  assert(hp);
108.  return hp->size == 0;
109. }

test.c(推排序和TOP-K问题）

1. #include"heap.h"
2. 
3. 
4. void HeapSort(int* a, int n)
5. {
6.  for (int i = (n - 1 - 1) / 2; i >= 0; i--)
7.  {
8.    AdjustDown(a, n, i);
9.  }
10.   int end = n - 1;
11.   while (end)
12.   {
13.     sweap(&a[0], &a[end]);
14.     AdjustDown(a, end, 0);
15.     end--;
16.   }
17. }
18. void CreateNDate()
19. {
20.   // 造数据
21.   int n = 10000;
22.   srand(time(0));
23.   const char* file = "data.txt";
24.   FILE* fin = fopen(file, "w");
25.   if (fin == NULL)
26.   {
27.     perror("fopen error");
28.     return;
29.   }
30. 
31.   for (size_t i = 0; i < n; ++i)
32.   {
33.     int x = rand() % 1000000;
34.     fprintf(fin, "%d\n", x);
35.   }
36. 
37.   fclose(fin);
38. }
39. 
40. void PrintTopK(int k)
41. {
42.   int k;
43.   printf("请输入k>:");
44.   scanf("%d", &k);
45.   int* kminheap = (int*)malloc(sizeof(int) * k);
46.   if (kminheap == NULL)
47.   {
48.     perror("malloc fail");
49.     return;
50.   }
51.   const char* file = "data.txt";
52.   FILE* fout = fopen(file, "r");
53.   if (fout == NULL)
54.   {
55.     perror("fopen error");
56.     return;
57.   }
58. 
59.   // 读取文件中前k个数
60.   for (int i = 0; i < k; i++)
61.   {
62.     fscanf(fout, "%d", &kminheap[i]);
63.   }
64.   // 建K个数的小堆
65.   for (int i = (k - 1 - 1) / 2; i >= 0; i--)
66.   {
67.     AdjustDown(kminheap, k, i);
68.   }
69. 
70.   // 读取剩下的N-K个数
71.   int x = 0;
72.   while (fscanf(fout, "%d", &x) > 0)
73.   {
74.     if (x > kminheap[0])
75.     {
76.       kminheap[0] = x;
77.       AdjustDown(kminheap, k, 0);
78.     }
79.   }
80. 
81.   printf("最大前%d个数：", k);
82.   for (int i = 0; i < k; i++)
83.   {
84.     printf("%d ", kminheap[i]);
85.   }
86.   printf("\n");
87. }

最后

今天的学习到这里就结束了，我们明天将开始二叉树的学习。到时候再会！

完！

二叉树——堆详解

前言：