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

前言：

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

一、堆的结构

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

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

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. }

最后

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

完！

二叉树——堆详解

前言：

一、堆的结构

二、向上调整和向下调整

2.1 向上调整

2.2 向下调整

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

三、堆的实现

3.1 堆的初始化

3.2 堆的销毁

3.3 堆的插入

3.4堆的删除

3.5 取堆顶元素

3.6 对堆判空

四、堆排序

五、TOP-K 问题

六、代码总览

heap.h

heap.c

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

最后

热门文章

最新文章

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

二叉树——堆详解

前言：

一、堆的结构

二、向上调整和向下调整

2.1 向上调整

2.2 向下调整

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

三、堆的实现

3.1 堆的初始化

3.2 堆的销毁

3.3 堆的插入

3.4堆的删除

3.5 取堆顶元素

3.6 对堆判空

四、堆排序

五、TOP-K 问题

六、代码总览

heap.h

heap.c

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

最后

热门文章

最新文章

相关电子书