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

TopK问题与堆排序_topk的堆算法

作者：从前慢现在也慢 | 2024-06-14 06:43:09

赞

踩

topk的堆算法

目录

1、堆的实现

（1）定义堆

（2）初始化堆

（3）交换父子结点

（4）打印堆内数据

（5）堆是否为空

（6）取堆顶数据

（7）销毁堆

（8）✳向上调整

（9）✳数据插入堆（拿最大堆举例，即：插入后仍是保持大堆）

对于插入堆来说，最大堆、最小堆都是向上调整

（10）✳向下调整

（11）✳删除堆顶数据（拿最大堆举例，即：删除后仍保持是大堆）

对于删除堆顶数据来说，最大堆、最小堆都是需要向下调整

※向下、向上调整的时间复杂度log2_N

2、建堆的应用

（1）TopK问题

实现TopK算法（最小的K个数）-- 建立小堆

（2）堆排序

堆排序  -  (向下调整建x堆+x堆)

排升序  -  (向下调整建大堆+大堆)

排降序  -  (向下调整建小堆+小堆)

建堆的时间复杂度O(N)证明

1、堆的实现

因为堆是一棵完全二叉树，所以使用数组结构，不会浪费空间。

所以，使用数组结构实现堆。

代码以大堆，作为插入堆、删除根节点为例子，后续不再说明：

（1）定义堆

可以看到，堆的结构定义和顺序表类似

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

（2）初始化堆

  1. //初始化堆
  2. void HeapInit(HP* hp)
  3. {
  4. 	assert(hp);
  5. 	hp->a = NULL;
  6. 	hp->size = hp->capacity = 0;
  7. }

（3）交换父子结点

  1. //交换父子结点数据
  2. void Swap(HPDataType* px, HPDataType* py)
  3. {
  4. 	HPDataType tmp = *px;
  5. 	*px = *py;
  6. 	*py = tmp;
  7. }

（4）打印堆内数据

  1. //打印堆内数据
  2. void HeapPrint(HP* hp)
  3. {
  4. 	for (int i = 0; i < hp->size; ++i)
  5. 	{
  6. 		printf("%d ", hp->a[i]);
  7. 	}
  8. 	printf("\n");
  9. }

（5）堆是否为空

  1. //堆为空
  2. bool HeapEmpty(HP* hp)
  3. {
  4. 	assert(hp);
  5.  
  6. 	return hp->size == 0;
  7. }

（6）取堆顶数据

  1. //获取堆顶数据
  2. HPDataType HeapTop(HP* hp)
  3. {
  4. 	assert(hp);
  5. 	assert(!HeapEmpty(hp));
  6.  
  7. 	return hp->a[0];
  8. }

（7）销毁堆

  1. //销毁堆
  2. void HeapDestroy(HP* hp)
  3. {
  4. 	assert(hp);
  5. 	free(hp->a);
  6. 	hp->capacity = hp->size = 0;
  7. }

（8）✳向上调整

插入堆如何实现呢？

注意：插入数据后，还要保证堆依旧是大堆（此处以大堆为列）

分析：

所以，需要向上调整。

  1. 先将元素插入到堆的末尾，即最后一个孩子之后
  2. 插入之后如果堆的性质遭到破坏，则将新插入节点顺着其双亲往上调整到合适位置即可

向上调整的执行逻辑：

  1. //向上调整（大堆）
  2. void AdjustUp(int* a, int child)
  3. {
  4. 	assert(a);
  5.  
  6. 	int parent = (child - 1) / 2;
  7. 	//while (parent >= 0)   //这样写有Bug！
  8. 	while (child > 0)
  9. 	{
  10. 		if (a[child] > a[parent])
  11. 		{
  12. 			/*HPDataType tmp = a[child];
  13. 			a[child] = a[parent];
  14. 			a[parent] = tmp;*/
  15. 			Swap(&a[child], &a[parent]);
  16.  
  17. 			child = parent;
  18. 			parent = (child - 1) / 2;
  19. 		}
  20. 		else
  21. 		{
  22. 			break;
  23. 		}
  24. 	}
  25. }

（9）✳数据插入堆（拿最大堆举例，即：插入后仍是保持大堆）

  1. //往堆插入数据
  2. void HeapPush(HP* hp, HPDataType x)
  3. {
  4. 	assert(hp);
  5. 	//不够就扩容
  6. 	if (hp->size == hp->capacity)
  7. 	{
  8. 		int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
  9. 		HPDataType* tmp = realloc(hp->a, sizeof(HPDataType) * newcapacity);
  10. 		if (tmp == NULL)
  11. 		{
  12. 			printf("realloc fail!\n");
  13. 			exit(-1);
  14. 		}
  15.  
  16. 		hp->a = tmp;
  17. 		hp->capacity = newcapacity;
  18. 	}
  19.  
  20. 	hp->a[hp->size] = x;
  21. 	hp->size++;
  22.  
  23. 	AdjustUp(hp->a, hp->size - 1);
  24. }

对于插入堆来说，最大堆、最小堆都是向上调整

区别：

最大堆向上调整，插入后的结点数据，要不改变最大堆（ps:定义  最大堆是每个节点的数据值都大于等于其子树数据值），影响了插入节点到根节点那段路径上的结点（ 产生变化！）：

  • 将插入结点作为child，与其父亲parent比较，如果a[child] > a[parent]，就交换节点数据值，直到child是根节点，才截至！

最小堆向上调整，插入后的结点数据，要不改变最小堆（ps:定义  最小堆是每个节点的数据值都小于等于其子树数据值），影响了插入节点到根节点那段路径上的结点（ 产生变化！）：

  • 将插入结点作为child，与其父亲parent比较，如果a[child] < a[parent]，就交换节点数据值，直到child是根节点，才截至！

（10）✳向下调整

分析：

删除堆顶数据，还要依旧保持是大堆，则需要向下调整：

  1. 将堆顶元素与堆中最后一个元素进行交换
  2. 删除堆中最后一个元素
  3. 将堆顶元素向下调整到满足堆特性为止

向下调整过程：

注意：向下调整的循环结束条件：（大堆为例！）

  1. 父亲  >=  大的孩子，则停止      即：父亲比两个孩子都大
  2. 调整到叶子结点         (叶子特征：没有左孩子，即：左孩子下标超出数组范围，就不存在了)
  1. //向下调整（大堆）
  2. void AdjustDown(int* a, int n, int parent)
  3. {
  4. 	assert(a);
  5.  
  6. 	int child = parent * 2 + 1;//左孩子
  7. 	while (child < n)
  8. 	{
  9. 		//选出大孩子
  10. 		if (child + 1 < n && a[child + 1] > a[child])
  11. 			child++;
  12. 		
  13. 		//交换 并 迭代 parent 和 child
  14. 		if (a[parent] < a[child])
  15. 		{
  16. 			Swap(&a[parent], &a[child]);
  17. 			parent = child;
  18. 			child = parent * 2 + 1;
  19. 		}
  20. 		else
  21. 		{
  22. 			break;
  23. 		}
  24. 	}
  25. }

（11）✳删除堆顶数据（拿最大堆举例，即：删除后仍保持是大堆）

  1. //删除堆顶数据
  2. void HeapPop(HP* hp)
  3. {
  4. 	assert(hp);
  5. 	assert(!HeapEmpty(&hp));
  6.  
  7. 	Swap(&hp->a[0], &hp->a[hp->size - 1]);//堆顶数据与末尾数据交换
  8. 	hp->size--;
  9.  
  10. 	AdjustDown(hp->a, hp->size, 0);
  11. }

对于删除堆顶数据来说，最大堆、最小堆都是需要向下调整

需要注意的是，根节点，也就是堆顶结点，我们直接删除是不行的！！   

需要将最后一个结点与根节点位置互换，因为我们删除尾结点（堆本质上是数组嘛~~~~~）是方便的！！！

然后再进行“  根结点  ” 向下调整...................

区别：

最大堆删除堆顶数据，看是否此时还仍然符合最大堆的要求，若不符合，那么就需要向下调整，调成符合最大堆的形式。

考虑到完全二叉树中，任意一个父亲节点左孩子存在，而右孩子不一定存在（细品！！！），所以我们需要判断，避免造成非法访问数组元素。如果右孩子存在，即：child + 1 < n ，右孩子大于左孩子，即：a[child + 1] > a[ child ](选出大孩子)。那么就child指向右孩子。

（即：该代码段是用child指向左右孩子中较大孩子）

如果说，a[child] > a[parent]，那么就交换父子结点，然后继续向下调整。

最小堆删除堆顶数据，看是否此时还仍然符合最小堆的要求，若不符合，那么就需要向下调整，调成符合最小堆的形式。

考虑到完全二叉树中，任意一个父亲节点左孩子存在，而右孩子不一定存在（细品！！！），所以我们需要判断，避免造成非法访问数组元素。如果右孩子存在，即：child + 1 < n ，右孩子小于左孩子，即：a[child + 1] < a[ child ](选出小孩子)。那么就child指向右孩子。

（即：该代码段是用child指向左右孩子中较小孩子）

如果说，a[child] < a[parent]，那么就交换父子结点，然后继续向下调整。

测试  【插入、删除大根堆】 的效果：

※向下、向上调整的时间复杂度log2_N

所以，向上向下调整都需要调整树的高度h次，即：时间复杂度为：O（log2_N）

堆的实现总代码：

  1. //Heap.h文件
  2. #pragma once
  3. #include<stdio.h>
  4. #include<stdlib.h>
  5. #include<assert.h>
  6. #include<stdbool.h>
  7.  
  8. //实现大堆
  9. typedef int HPDataType;
  10. //定义堆
  11. typedef struct Heap
  12. {
  13. 	HPDataType* a;
  14. 	int size;
  15. 	int capacity;
  16. }HP;
  17.  
  18.  
  19. //初始化堆
  20. void HeapInit(HP* hp);
  21.  
  22. //交换父子结点数据
  23. void Swap(HPDataType* px, HPDataType* py);
  24.  
  25. //打印堆内数据
  26. void HeapPrint(HP* hp);
  27.  
  28. //堆为空
  29. bool HeapEmpty(HP* hp);
  30.  
  31. //销毁堆
  32. void HeapDestroy(HP* hp);
  33.  
  34. //数据插入堆
  35. void HeapPush(HP* hp, HPDataType x);
  36.  
  37. //向上调整
  38. void AdjustUp(int* a, int child);
  39.  
  40. //删除堆顶数据
  41. void HeapPop(HP* hp);
  42.  
  43. //向下调整
  44. void AdjustDown(int* a, int n, int parent);
  45.  
  46. //获取堆顶数据
  47. HPDataType HeapTop(HP* hp);
  1. //Heap.c文件
  2. #define _CRT_SECURE_NO_WARNINGS
  3. #include"Heap.h"
  4.  
  5. //初始化堆
  6. void HeapInit(HP* hp)
  7. {
  8. 	assert(hp);
  9.  
  10. 	hp->a = NULL;
  11. 	hp->size = hp->capacity = 0;
  12. }
  13. //销毁堆
  14. void HeapDestroy(HP* hp)
  15. {
  16. 	assert(hp);
  17. 	free(hp->a);
  18. 	hp->capacity = hp->size = 0;
  19. }
  20. //交换父子结点数据
  21. void Swap(HPDataType* px, HPDataType* py)
  22. {
  23. 	HPDataType tmp = *px;
  24. 	*px = *py;
  25. 	*py = tmp;
  26. }
  27. //获取堆顶数据
  28. HPDataType HeapTop(HP* hp)
  29. {
  30. 	assert(hp);
  31. 	assert(!HeapEmpty(hp));
  32.  
  33. 	return hp->a[0];
  34. }
  35. 向上调整（大堆）
  36. //void AdjustUp(int* a, int child)
  37. //{
  38. //	assert(a);
  39. //
  40. //	int parent = (child - 1) / 2;
  41. //	//while (parent >= 0)
  42. //	while (child > 0)
  43. //	{
  44. //		if (a[child] > a[parent])
  45. //		{
  46. //			/*HPDataType tmp = a[child];
  47. //			a[child] = a[parent];
  48. //			a[parent] = tmp;*/
  49. //			Swap(&a[child], &a[parent]);
  50. //
  51. //			child = parent;
  52. //			parent = (child - 1) / 2;
  53. //		}
  54. //		else
  55. //		{
  56. //			break;
  57. //		}
  58. //	}
  59. //}
  60. //向上调整（小堆）
  61. void AdjustUp(int* a, int child)
  62. {
  63. 	assert(a);
  64.  
  65. 	int parent = (child - 1) / 2;
  66. 	//while (parent >= 0)
  67. 	while (child > 0)
  68. 	{
  69. 		if (a[child] < a[parent])
  70. 		{
  71. 			/*HPDataType tmp = a[child];
  72. 			a[child] = a[parent];
  73. 			a[parent] = tmp;*/
  74. 			Swap(&a[child], &a[parent]);
  75.  
  76. 			child = parent;
  77. 			parent = (child - 1) / 2;
  78. 		}
  79. 		else
  80. 		{
  81. 			break;
  82. 		}
  83. 	}
  84. }
  85. //往堆插入数据
  86. void HeapPush(HP* hp, HPDataType x)
  87. {
  88. 	assert(hp);
  89. 	//不够就扩容
  90. 	if (hp->size == hp->capacity)
  91. 	{
  92. 		int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
  93. 		HPDataType* tmp = realloc(hp->a, sizeof(HPDataType) * newcapacity);
  94. 		if (tmp == NULL)
  95. 		{
  96. 			printf("realloc fail!\n");
  97. 			exit(-1);
  98. 		}
  99.  
  100. 		hp->a = tmp;
  101. 		hp->capacity = newcapacity;
  102. 	}
  103.  
  104. 	hp->a[hp->size] = x;
  105. 	hp->size++;
  106.  
  107. 	AdjustUp(hp->a, hp->size - 1);
  108. }
  109. //判断堆是否为空
  110. bool HeapEmpty(HP* hp)
  111. {
  112. 	assert(hp);
  113.  
  114. 	return hp->size == 0;
  115. }
  116. //堆的数据个数
  117. int HeapSize(HP* hp)
  118. {
  119. 	assert(hp);
  120.  
  121. 	return hp->size;
  122. }
  123. //打印堆内数据
  124. void HeapPrint(HP* hp)
  125. {
  126. 	for (int i = 0; i < hp->size; ++i)
  127. 	{
  128. 		printf("%d ", hp->a[i]);
  129. 	}
  130. 	printf("\n");
  131. }
  132. 向下调整（大堆）
  133. //void AdjustDown(int* a, int n, int parent)
  134. //{
  135. //	assert(a);
  136. //
  137. //	int child = parent * 2 + 1;//左孩子
  138. //	while (child < n)
  139. //	{
  140. //		//选出大孩子
  141. //		if (child + 1 < n && a[child + 1] > a[child])
  142. //			child++;
  143. //		
  144. //		//交换 并 迭代 parent 和 child
  145. //		if (a[parent] < a[child])
  146. //		{
  147. //			Swap(&a[parent], &a[child]);
  148. //			parent = child;
  149. //			child = parent * 2 + 1;
  150. //		}
  151. //		else
  152. //		{
  153. //			break;
  154. //		}
  155. //	}
  156. //}
  157. //向下调整（小堆）
  158. void AdjustDown(int* a, int n, int parent)
  159. {
  160. 	assert(a);
  161.  
  162. 	int child = parent * 2 + 1;//左孩子
  163. 	while (child < n)
  164. 	{
  165. 		//选出小孩子
  166. 		if (child + 1 < n && a[child + 1] < a[child])
  167. 			child++;
  168.  
  169. 		//交换 并 迭代 parent 和 child
  170. 		if (a[parent] > a[child])
  171. 		{
  172. 			Swap(&a[parent], &a[child]);
  173. 			parent = child;
  174. 			child = parent * 2 + 1;
  175. 		}
  176. 		else
  177. 		{
  178. 			break;
  179. 		}
  180. 	}
  181. }
  182. //删除堆顶数据
  183. void HeapPop(HP* hp)
  184. {
  185. 	assert(hp);
  186. 	assert(!HeapEmpty(&hp));
  187.  
  188. 	Swap(&hp->a[0], &hp->a[hp->size - 1]);//堆顶数据与末尾数据交换
  189. 	hp->size--;
  190.  
  191. 	AdjustDown(hp->a, hp->size, 0);
  192. }
  1. //Test.c文件
  2. #define _CRT_SECURE_NO_WARNINGS
  3. #include"Heap.h"
  4.  
  5. //在N个数中找出最大的前K个最大值 （或者最小的前K个最小值）
  6.  
  7. int main()
  8. {
  9. 	int a[] = { 70,56,30,25,15,10,75 };
  10. 	HP hp;
  11. 	HeapInit(&hp);
  12. 	for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
  13. 	{
  14. 		HeapPush(&hp, a[i]);
  15. 	}
  16. 	HeapPrint(&hp);
  17.  
  18. 	HeapPop(&hp);
  19. 	HeapPrint(&hp);
  20.  
  21. 	HeapPop(&hp);
  22. 	HeapPrint(&hp);
  23.  
  24. 	//销毁堆
  25. 	HeapDestroy(&hp);
  26.  
  27. 	return 0;
  28. }

2、建堆的应用

  1. topk问题
  2. 堆排序算法

（1）TopK问题

首先想想为什么要用堆实现Topk问题？在N非常大的时候，其他算法为什么不行？

以选最大的K个数为例，建立小堆。

建立K个数的小堆，最终达到选出N个数中最大的K个数，在这个过程中需要注意的是：

  1. 选最大的K个数，是建立小堆。因为小堆的堆顶数据最小的，而用剩下的N-K个数去和最小的比较...然后大于它...就取代，就会保证每次选出的K个数都是到目前为止最大的K个数。
  2. 因为K<<N，所以通过该方法实现了仅仅用K个空间就可以实现N个数据中的Topk问题。空间节约了，而且没有多余去管其他的N-K个数具体的大小，针对性的解决了要求的K个数。

实现TopK算法（最小的K个数）-- 建立小堆

TopK算法（Test.c文件）

  1. //Test.c文件
  2. #define _CRT_SECURE_NO_WARNINGS
  3. #include"Heap.h"
  4.  
  5. //从N个数中，选出K个最大的数
  6. //（只有建立 【小堆】 一种办法，大堆不行）
  7. void PrintTopK(int* a, int n, int k)
  8. {
  9. 	HP hp;
  10. 	HeapInit(&hp);
  11. 	// 1. 建堆--用a中的K个数创建一个小堆
  12. 	for (int i = 0; i < k; ++i)
  13. 	{
  14. 		HeapPush(&hp, a[i]);//小堆的HeapPush
  15. 	}
  16.  
  17. 	// 2. 将剩余N-K个元素依次与堆顶数据比较，比他大，就替换他，进堆
  18. 	for (int i = k; i < n; ++i)
  19. 	{
  20. 		if (a[i] > HeapTop(&hp))
  21. 		{
  22. 			//方法1
  23. 			//HeapPop(&hp);//小堆的HeapPop
  24. 			//HeapPush(&hp, a[i]);
  25.  
  26. 			//方法2
  27. 			hp.a[0] = a[i];
  28. 			AdjustDown(hp.a, hp.size, 0);//==>为了保持是小堆
  29. 		}
  30. 	}
  31. 	HeapPrint(&hp);
  32.  
  33. 	//HeapDestroy(&hp);
  34. }
  35. void TestTopk()
  36. {
  37. 	int n = 10000;
  38. 	int* a = (int*)malloc(sizeof(int) * n);
  39. 	srand(time(0));
  40. 	for (int i = 0; i < n; ++i)
  41. 	{
  42. 		//随机生成数字，%100w就保证了数字小于100w
  43. 		a[i] = rand() % 1000000;
  44. 	}
  45. 	//手动设置10个大于100w的数字（  即：要选出的K个最大数  ）
  46. 	a[5] = 1000000 + 1;
  47. 	a[1231] = 1000000 + 2;
  48. 	a[531] = 1000000 + 3;
  49. 	a[5121] = 1000000 + 4;
  50. 	a[115] = 1000000 + 5;
  51. 	a[2335] = 1000000 + 6;
  52. 	a[9999] = 1000000 + 7;
  53. 	a[76] = 1000000 + 8;
  54. 	a[423] = 1000000 + 9;
  55. 	a[3144] = 1000000 + 10;
  56. 	PrintTopK(a, n, 10);
  57. }
  58. int main()
  59. {
  60. 	TestTopk();
  61.  
  62. 	return 0;
  63. }
  1. //Heap.h文件
  2. #pragma once
  3. #include<stdio.h>
  4. #include<stdlib.h>
  5. #include<assert.h>
  6. #include<stdbool.h>
  7.  
  8. //实现大堆
  9. typedef int HPDataType;
  10. //定义堆
  11. typedef struct Heap
  12. {
  13. 	HPDataType* a;
  14. 	int size;
  15. 	int capacity;
  16. }HP;
  17.  
  18.  
  19. //初始化堆
  20. void HeapInit(HP* hp);
  21.  
  22. //交换父子结点数据
  23. void Swap(HPDataType* px, HPDataType* py);
  24.  
  25. //打印堆内数据
  26. void HeapPrint(HP* hp);
  27.  
  28. //堆为空
  29. bool HeapEmpty(HP* hp);
  30.  
  31. //销毁堆
  32. void HeapDestroy(HP* hp);
  33.  
  34. //数据插入堆
  35. void HeapPush(HP* hp, HPDataType x);
  36.  
  37. //向上调整
  38. void AdjustUp(int* a, int child);
  39.  
  40. //删除堆顶数据
  41. void HeapPop(HP* hp);
  42.  
  43. //向下调整
  44. void AdjustDown(int* a, int n, int parent);
  45.  
  46. //获取堆顶数据
  47. HPDataType HeapTop(HP* hp);
  1. //Heap.c文件
  2. #define _CRT_SECURE_NO_WARNINGS
  3. #include"Heap.h"
  4.  
  5. //初始化堆
  6. void HeapInit(HP* hp)
  7. {
  8. 	assert(hp);
  9.  
  10. 	hp->a = NULL;
  11. 	hp->size = hp->capacity = 0;
  12. }
  13. //销毁堆
  14. void HeapDestroy(HP* hp)
  15. {
  16. 	assert(hp);
  17. 	free(hp->a);
  18. 	hp->capacity = hp->size = 0;
  19. }
  20. //交换父子结点数据
  21. void Swap(HPDataType* px, HPDataType* py)
  22. {
  23. 	HPDataType tmp = *px;
  24. 	*px = *py;
  25. 	*py = tmp;
  26. }
  27. //获取堆顶数据
  28. HPDataType HeapTop(HP* hp)
  29. {
  30. 	assert(hp);
  31. 	assert(!HeapEmpty(hp));
  32.  
  33. 	return hp->a[0];
  34. }
  35. //向上调整（小堆）
  36. void AdjustUp(int* a, int child)
  37. {
  38. 	assert(a);
  39.  
  40. 	int parent = (child - 1) / 2;
  41. 	//while (parent >= 0)
  42. 	while (child > 0)
  43. 	{
  44. 		if (a[child] < a[parent])
  45. 		{
  46. 			/*HPDataType tmp = a[child];
  47. 			a[child] = a[parent];
  48. 			a[parent] = tmp;*/
  49. 			Swap(&a[child], &a[parent]);
  50.  
  51. 			child = parent;
  52. 			parent = (child - 1) / 2;
  53. 		}
  54. 		else
  55. 		{
  56. 			break;
  57. 		}
  58. 	}
  59. }
  60. //往堆插入数据
  61. void HeapPush(HP* hp, HPDataType x)
  62. {
  63. 	assert(hp);
  64. 	//不够就扩容
  65. 	if (hp->size == hp->capacity)
  66. 	{
  67. 		int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
  68. 		HPDataType* tmp = realloc(hp->a, sizeof(HPDataType) * newcapacity);
  69. 		if (tmp == NULL)
  70. 		{
  71. 			printf("realloc fail!\n");
  72. 			exit(-1);
  73. 		}
  74.  
  75. 		hp->a = tmp;
  76. 		hp->capacity = newcapacity;
  77. 	}
  78.  
  79. 	hp->a[hp->size] = x;
  80. 	hp->size++;
  81.  
  82. 	AdjustUp(hp->a, hp->size - 1);
  83. }
  84. //判断堆是否为空
  85. bool HeapEmpty(HP* hp)
  86. {
  87. 	assert(hp);
  88.  
  89. 	return hp->size == 0;
  90. }
  91. //堆的数据个数
  92. int HeapSize(HP* hp)
  93. {
  94. 	assert(hp);
  95.  
  96. 	return hp->size;
  97. }
  98. //打印堆内数据
  99. void HeapPrint(HP* hp)
  100. {
  101. 	for (int i = 0; i < hp->size; ++i)
  102. 	{
  103. 		printf("%d ", hp->a[i]);
  104. 	}
  105. 	printf("\n");
  106. }
  107. //向下调整（小堆）
  108. void AdjustDown(int* a, int n, int parent)
  109. {
  110. 	assert(a);
  111.  
  112. 	int child = parent * 2 + 1;//左孩子
  113. 	while (child < n)
  114. 	{
  115. 		//选出小孩子
  116. 		if (child + 1 < n && a[child + 1] < a[child])
  117. 			child++;
  118.  
  119. 		//交换 并 迭代 parent 和 child
  120. 		if (a[parent] > a[child])
  121. 		{
  122. 			Swap(&a[parent], &a[child]);
  123. 			parent = child;
  124. 			child = parent * 2 + 1;
  125. 		}
  126. 		else
  127. 		{
  128. 			break;
  129. 		}
  130. 	}
  131. }
  132. //删除堆顶数据
  133. void HeapPop(HP* hp)
  134. {
  135. 	assert(hp);
  136. 	assert(!HeapEmpty(&hp));
  137.  
  138. 	Swap(&hp->a[0], &hp->a[hp->size - 1]);//堆顶数据与末尾数据交换
  139. 	hp->size--;
  140.  
  141. 	AdjustDown(hp->a, hp->size, 0);
  142. }

测试效果 

（2）堆排序

堆排序 - 升序  -  空间复杂度为O(N)的写法    （不推荐）

堆排序算法（Test.c文件）

该算法是建立小堆，并且用了HeapPush等建堆操作；所以是额外开辟使用了空间，并且还得事先实现堆以及堆的操作才能做。

而堆本身就是数组，那么能否直接对数组a进行构建堆？（不用堆的任何相关操作~）

  1. //Test.c文件
  2. #define _CRT_SECURE_NO_WARNINGS
  3. #include"Heap.h"
  4.  
  5. //堆排序 - 升序  - 空间复杂度（ O(N) ）  
  6. //降序同理，Push、Pop小堆变大堆即可
  7. void HeapSort(int* a, int n)
  8. {
  9. 	HP hp;
  10. 	HeapInit(&hp);
  11. 	//建立一个小堆
  12. 	for (int i = 0; i < n; ++i)
  13. 	{
  14. 		HeapPush(&hp, a[i]);//小堆的HeapPush
  15. 	}
  16.  
  17. 	//Pop  N 次
  18. 	for (int i = 0; i < n; ++i)
  19. 	{
  20. 		a[i] = HeapTop(&hp);
  21. 		HeapPop(&hp);//小堆的HeapPop
  22. 	}
  23. 	//HeapDestroy(&hp);
  24. }
  25. int main()
  26. {
  27. 	int a[] = { 70,56,30,25,15,10,75 };
  28. 	for (int i = 0; i < sizeof(a) / sizeof(a[0]); ++i)
  29. 	{
  30. 		printf("%d ", a[i]);
  31. 	}
  32. 	printf("\n");
  33.  
  34. 	HeapSort(a, sizeof(a) / sizeof(a[0]));
  35.  
  36. 	for (int i = 0; i < sizeof(a) / sizeof(a[0]); ++i)
  37. 	{
  38. 		printf("%d ", a[i]);
  39. 	}
  40. 	printf("\n");
  41. 	return 0;
  42. }

该程序空间复杂度是O(N)，那么能否优化到O(1)呢？

（即：不能用Heap避免了HeapPush开辟新空间，直接对数组a进行操作）

堆排序 - 升序  -  空间复杂度为 O(1) 的写法    （推荐！） 

考虑到原来使用了HeapPush建堆，新开辟了N个空间。所以空间复杂度是O（N），而优化到O（1）即优化建堆的操作。

所以，优化建堆的操作就是对数组a直接操作，不开辟新空间。其有两种方式：

  1. 向上调整  （依次加入）
  2. 向下调整  （倒着走）

那么建堆完成后，如何实现升序呢？

 所以，排升序，用大堆+向下调整建堆方式

堆排序  -  (向下调整建x堆+x堆)

堆排序：

  1. 排升序，建大堆
  2. 排降序，建小堆

*注释：大小堆，在堆排序中的区别就体现在AdjustDown函数实现的是大堆还是小堆

  1. void HeapSort(int* a, int n)
  2. {
  3. 	//把a构建成堆（向下调整）
  4. 	//注意：需要找到 [最后一个节点] 的 [父亲节点] ，从那开始，向下调整
  5.  
  6. 	int end = n - 1;//最后一个节点
  7. 	for (int i = (end - 1) / 2; i >= 0; i--)
  8. 	{
  9. 		AdjustDown(a, n, i);
  10. 	}
  11.  
  12. 	//实现升序
  13. 	end = n - 1;//最后一个数
  14. 	for (int i = end; i > 0; i--)
  15. 	{
  16. 		Swap(&a[i], &a[0]);
  17. 		AdjustDown(a, i, 0);
  18. 	}
  19. }

排升序  -  (向下调整建大堆+大堆)

  1. //向下调整（大堆）
  2. void AdjustDown(int* a, int n, int parent);
  3. //堆排序 - 升序  -（向下调整建大堆+大堆）
  4. void HeapSort(int* a, int n)
  5. {
  6. 	//把a构建成堆（向下调整）
  7. 	//注意：需要找到 [最后一个节点] 的 [父亲节点] ，从那开始，向下调整
  8.  
  9. 	int end = n - 1;//最后一个节点
  10. 	for (int i = (end - 1) / 2; i >= 0; i--)
  11. 	{
  12. 		AdjustDown(a, n, i);
  13. 	}
  14.  
  15. 	//实现升序
  16. 	end = n - 1;//最后一个数
  17. 	for (int i = end; i > 0; i--)
  18. 	{
  19. 		Swap(&a[i], &a[0]);
  20. 		AdjustDown(a, i, 0);
  21. 	}
  22. }
  23. //向下调整（大堆）
  24. void AdjustDown(int* a, int n, int parent)
  25. {
  26. 	assert(a);
  27.  
  28. 	int child = parent * 2 + 1;//左孩子
  29. 	while (child < n)
  30. 	{
  31. 		//选出大孩子
  32. 		if (child + 1 < n && a[child + 1] > a[child])
  33. 			child++;
  34.  
  35. 		//交换 并 迭代 parent 和 child
  36. 		if (a[parent] < a[child])
  37. 		{
  38. 			Swap(&a[parent], &a[child]);
  39. 			parent = child;
  40. 			child = parent * 2 + 1;
  41. 		}
  42. 		else
  43. 		{
  44. 			break;
  45. 		}
  46. 	}
  47. }

整体代码

  1. //堆排序 - 升序 -（向下调整建大堆+大堆）
  2. void HeapSort(int* a, int n)
  3. {
  4. 	//建堆操作：
  5. 	//方法1：
  6. 	//把a构建成堆（向上调整）
  7. 	/*for (int i = 0; i < n; i++)
  8. 	{
  9. 		AdjustUp(a, i);
  10. 	}
  11. 	*/
  12.  
  13. 	//方法2：
  14. 	//把a构建成堆（向下调整）
  15. 	//注意：需要找到 [最后一个节点] 的 [父亲节点] ，从那开始，向下调整
  16.  
  17. 	int end = n - 1;//最后一个节点
  18. 	for (int i = (end - 1) / 2; i >= 0; i--)
  19. 	{
  20. 		AdjustDown(a, n, i);
  21. 	}
  22.  
  23. 	//实现升序
  24. 	end = n - 1;//最后一个数
  25. 	for (int i = end; i > 0; i--)
  26. 	{
  27. 		Swap(&a[i], &a[0]);
  28. 		AdjustDown(a, i, 0);
  29. 	}
  30. }
  31. int main()
  32. {
  33. 	int a[] = { 70,56,30,25,15,10,75,33,50,69 };
  34. 	for (int i = 0; i < sizeof(a) / sizeof(a[0]); ++i)
  35. 	{
  36. 		printf("%d ", a[i]);
  37. 	}
  38. 	printf("\n");
  39.  
  40. 	HeapSort(a, sizeof(a) / sizeof(a[0]));
  41.  
  42. 	for (int i = 0; i < sizeof(a) / sizeof(a[0]); ++i)
  43. 	{
  44. 		printf("%d ", a[i]);
  45. 	}
  46. 	printf("\n");
  47. 	return 0;
  48. }

 同理，堆排序 - 排降序是建立小堆

排降序  -  (向下调整建小堆+小堆)

  1. //向下调整（小堆）
  2. void AdjustDown(int* a, int n, int parent);
  3. //堆排序 - 降序 
  4. void HeapSort(int* a, int n)
  5. {
  6. 	//把a构建成堆（向下调整）
  7. 	//注意：需要找到 [最后一个节点] 的 [父亲节点] ，从那开始，向下调整
  8.  
  9. 	int end = n - 1;//最后一个节点
  10. 	for (int i = (end - 1) / 2; i >= 0; i--)
  11. 	{
  12. 		AdjustDown(a, n, i);
  13. 	}
  14.  
  15. 	//实现降序
  16. 	end = n - 1;//最后一个数
  17. 	for (int i = end; i > 0; i--)
  18. 	{
  19. 		Swap(&a[i], &a[0]);
  20. 		AdjustDown(a, i, 0);
  21. 	}
  22. }
  23. //向下调整（小堆）
  24. void AdjustDown(int* a, int n, int parent)
  25. {
  26. 	assert(a);
  27.  
  28. 	int child = parent * 2 + 1;//左孩子
  29. 	while (child < n)
  30. 	{
  31. 		//选出小孩子
  32. 		if (child + 1 < n && a[child + 1] < a[child])
  33. 			child++;
  34.  
  35. 		//交换 并 迭代 parent 和 child
  36. 		if (a[parent] > a[child])
  37. 		{
  38. 			Swap(&a[parent], &a[child]);
  39. 			parent = child;
  40. 			child = parent * 2 + 1;
  41. 		}
  42. 		else
  43. 		{
  44. 			break;
  45. 		}
  46. 	}
  47. }

整体代码：

  1. //堆排序 - 降序 
  2. void HeapSort(int* a, int n)
  3. {
  4. 	//建堆操作：
  5. 	//方法1：
  6. 	//把a构建成堆（向上调整）
  7. 	/*for (int i = 0; i < n; i++)
  8. 	{
  9. 		AdjustUp(a, i);
  10. 	}
  11. 	*/
  12.  
  13. 	//方法2：
  14. 	//把a构建成堆（向下调整）
  15. 	//注意：需要找到 [最后一个节点] 的 [父亲节点] ，从那开始，向下调整
  16.  
  17. 	int end = n - 1;//最后一个节点
  18. 	for (int i = (end - 1) / 2; i >= 0; i--)
  19. 	{
  20. 		AdjustDown(a, n, i);
  21. 	}
  22.  
  23. 	//实现降序
  24. 	end = n - 1;//最后一个数
  25. 	for (int i = end; i > 0; i--)
  26. 	{
  27. 		Swap(&a[i], &a[0]);
  28. 		AdjustDown(a, i, 0);
  29. 	}
  30. }
  31. int main()
  32. {
  33. 	int a[] = { 70,56,30,25,15,10,75,33,50,69 };
  34. 	for (int i = 0; i < sizeof(a) / sizeof(a[0]); ++i)
  35. 	{
  36. 		printf("%d ", a[i]);
  37. 	}
  38. 	printf("\n");
  39.  
  40. 	HeapSort(a, sizeof(a) / sizeof(a[0]));
  41.  
  42. 	for (int i = 0; i < sizeof(a) / sizeof(a[0]); ++i)
  43. 	{
  44. 		printf("%d ", a[i]);
  45. 	}
  46. 	printf("\n");
  47. 	return 0;
  48. }

建堆的时间复杂度O(N)证明

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

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