devbox
Gausst松鼠会
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

二叉树——堆详解

作者：Gausst松鼠会 | 2024-06-09 04:47:13

赞

踩

二叉树——堆详解

目录

前言：

一、堆的结构

二、向上调整和向下调整

        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问题）

最后

前言：

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

一、堆的结构

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

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

  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 (child + 1 < n && a[child] > a[child+1])//此步的目的是找到最小的,并判断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 (child + 1 < n && 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. }

最后

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

完！

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Gausst松鼠会/article/detail/692669
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号