• 数据结构-堆排序及其复杂度计算

    目录

    1.堆排序

    1.1 向上调整建堆

    1.2 向下调整建堆

    2. 两种建堆方式的时间复杂度比较

    2.1 向下调整建堆的时间复杂度

    2.2 向上调整建堆的时间复杂度

    Topk问题

    上节内容，我们讲了堆的实现，同时还包含了向上调整法和向下调整法，最后我们用堆实现了对数据的排序：

    1. int main()
    2. {
    3. 	HP hp;
    4. 	HeapInit(&hp);
    5. 	int arr[] = { 65,100,70,32,50,60 };
    6. 	int i = 0;
    7. 	for (i = 0; i < sizeof(arr) / sizeof(int); i++)
    8. 	{
    9. 		HeapPush(&hp, arr[i]);
    10. 	}
    11. 	while (!HeapEmpty(&hp))
    12. 	{
    13. 		HeapDatatype top = HeapTop(&hp);
    14. 		printf("%d ", top);
    15. 		HeapPop(&hp);
    16. 	}
    17. 	return 0;
    18. }

    那以上代码能实现对数据的排序吗?

    答案是可以的，但是以上方式有两个弊端：

    1. 要先写一个堆，太麻烦

    2. 空间复杂度+拷贝数据。

    1.堆排序

    上节内容中，用堆对数据进行排序，是将数据一个一个插入堆，然后再调整排序的，那我们能不能直接把数据就建成一个堆？

    当然可以，建堆有两种方式：向上调整建堆、向下调整建堆。

    1.1 向上调整建堆

    我们先来讲向上调整建堆：

    向上调整建堆其实还是插入堆的逻辑，要求前面的数据必须是一个堆，下标从1开始是因为一个数据本身就可以被看做一个堆，然后向上调整。 

    下图就是我们对一个数组数据进行向上调整建堆后的结果，可以看出来，此时我们建的是一个小堆： 

    现在问题来了，我们要把数据排为升序，建大堆还是建小堆好？

    先说结论：升序 -- 建大堆    降序 -- 建小堆。 

    假设我们要得到升序，此时又建的是小堆，那我们就把选出的最小的数据放在下标为0的位置，要想继续选出次小的数据放在下标为1的位置，就要把剩下的数据看做堆，这样堆的关系就全乱了，只能重新建堆，代价太大。

    而如果我们建大堆，向下调整选出最大的数据，首尾交换，把最大的数据放在最后一个下标的位置，然后隔离最后一个数据，把其他数据看做一个堆，再向下调整选出次大的，首尾交换......直到所有的数据被排好序，此时得到的就是数据升序。

    代码如下：

    1. #define  _CRT_SECURE_NO_WARNINGS 1
    2. #include
    3.  
    4. typedef int HeapDatatype;
    5.  
    6. swap(HeapDatatype* p1, HeapDatatype* p2)
    7. {
    8. 	HeapDatatype tmp = *p1;
    9. 	*p1 = *p2;
    10. 	*p2 = tmp;
    11. }
    12. //向上调整法
    13. void AdjustUp(HeapDatatype* a, int child)
    14. {
    15. 	int parent = (child - 1) / 2;
    16. 	while (child > 0)
    17. 	{
    18. 		if (a[parent] < a[child])
    19. 		{
    20. 			HeapDatatype p = a[parent];
    21. 			a[parent] = a[child];
    22. 			a[child] = p;
    23. 			child = parent;
    24. 			parent = (child - 1) / 2;
    25. 		}
    26. 		else
    27. 		{
    28. 			break;
    29. 		}
    30. 	}
    31. }
    32. //向下调整法
    33. void AdjustDown(HeapDatatype* a, int n, int parent)
    34. {
    35. 	int child = parent * 2 + 1;
    36. 	while (child < n)
    37. 	{
    38. 		if (child + 1 < n && a[child] < a[child + 1])
    39. 		{
    40. 			child++;
    41. 		}
    42. 		if (a[parent] < a[child])
    43. 		{
    44. 			swap(&a[parent], &a[child]);
    45. 			parent = child;
    46. 			child = parent * 2 + 1;
    47. 		}
    48. 		else
    49. 		{
    50. 			break;
    51. 		}
    52. 	}
    53. }
    54. //堆排序
    55. void HeapSort(int* a, int n)
    56. {
    57. 	//建堆 - 向上调整建堆
    58. 	for (int i = 1; i < n; i++)
    59. 	{
    60. 		AdjustUp(a, i);
    61. 	}
    62. 	//向下调整得到次大数据
    63. 	int end = n - 1;
    64. 	while (end > 0)
    65. 	{
    66. 		swap(&a[0], &a[end]);
    67. 		AdjustDown(a, end, 0);
    68. 		end--;
    69. 	}
    70. }
    71.  
    72. int main()
    73. {
    74. 	int a[] = { 7,8,3,5,1,9,5,4 };
    75. 	HeapSort(a, sizeof(a) / sizeof(int));
    76. 	return 0;
    77. }

    我们建的是大堆，最后得到的就是升序： 

    要得到数据降序，就要建小堆，向下调整选出最小的数据，首尾交换，把最小数据放在最后一个下标的位置，隔离最后一个数据，把其他数据看做一个堆，再向下调整选出次小的数据，首尾交换......直到所有数据都被拍好序，这就得到数据降序。

    代码如下：（只需将向下调整和向上调整中的'<'改为'>'即可）

    1. #define  _CRT_SECURE_NO_WARNINGS 1
    2. #include
    3.  
    4. typedef int HeapDatatype;
    5.  
    6. swap(HeapDatatype* p1, HeapDatatype* p2)
    7. {
    8. 	HeapDatatype tmp = *p1;
    9. 	*p1 = *p2;
    10. 	*p2 = tmp;
    11. }
    12. //向上调整法
    13. void AdjustUp(HeapDatatype* a, int child)
    14. {
    15. 	int parent = (child - 1) / 2;
    16. 	while (child > 0)
    17. 	{
    18. 		if (a[parent] > a[child])
    19. 		{
    20. 			HeapDatatype p = a[parent];
    21. 			a[parent] = a[child];
    22. 			a[child] = p;
    23. 			child = parent;
    24. 			parent = (child - 1) / 2;
    25. 		}
    26. 		else
    27. 		{
    28. 			break;
    29. 		}
    30. 	}
    31. }
    32. //向下调整法
    33. void AdjustDown(HeapDatatype* a, int n, int parent)
    34. {
    35. 	int child = parent * 2 + 1;
    36. 	while (child < n)
    37. 	{
    38. 		if (child + 1 < n && a[child] > a[child + 1])
    39. 		{
    40. 			child++;
    41. 		}
    42. 		if (a[parent] > a[child])
    43. 		{
    44. 			swap(&a[parent], &a[child]);
    45. 			parent = child;
    46. 			child = parent * 2 + 1;
    47. 		}
    48. 		else
    49. 		{
    50. 			break;
    51. 		}
    52. 	}
    53. }
    54. //堆排序
    55. void HeapSort(int* a, int n)
    56. {
    57. 	//建堆 - 向上调整建堆
    58. 	for (int i = 1; i < n; i++)
    59. 	{
    60. 		AdjustUp(a, i);
    61. 	}
    62. 	//向下调整得到次小数据
    63. 	int end = n - 1;
    64. 	while (end > 0)
    65. 	{
    66. 		swap(&a[0], &a[end]);
    67. 		AdjustDown(a, end, 0);
    68. 		end--;
    69. 	}
    70. }
    71.  
    72. int main()
    73. {
    74. 	int a[] = { 7,8,3,5,1,9,5,4 };
    75. 	HeapSort(a, sizeof(a) / sizeof(int));
    76. 	return 0;
    77. }

    由于我们建的是小堆，所以得到的就是数据降序： 

    注意：不论是升序还是降序，数据都是从后往前放的，这样就不会使堆的关系混乱。 

    1.2 向下调整建堆

    我们可以看到，堆排序使用向上调整建堆，还要写两个函数：向下调整函数、向上调整函数。

    那我们想用一个向下调整函数就解决问题呢？

    这就需要向下调整建堆：

    向下调整建堆要求根节点的左右子树都是大堆（小堆），如果左右子树不满足大堆，我们只需要确保左右子树的左右子树是大堆（小堆）即可，如果又不是，我们再往下找，所以只要使所有父节点的左右子树都是大堆（小堆）就行，那我们就倒着调整，因为叶子节点本身就是一个堆，所以不需要调整，那就从最后一个节点的父节点开始调整。

    代码如下：

    1. #define  _CRT_SECURE_NO_WARNINGS 1
    2. #include
    3.  
    4. typedef int HeapDatatype;
    5.  
    6. swap(HeapDatatype* p1, HeapDatatype* p2)
    7. {
    8. 	HeapDatatype tmp = *p1;
    9. 	*p1 = *p2;
    10. 	*p2 = tmp;
    11. }
    12.  
    13. //向下调整法
    14. void AdjustDown(HeapDatatype* a, int n, int parent)
    15. {
    16. 	int child = parent * 2 + 1;
    17. 	while (child < n)
    18. 	{
    19. 		if (child + 1 < n && a[child] > a[child + 1])
    20. 		{
    21. 			child++;
    22. 		}
    23. 		if (a[parent] > a[child])
    24. 		{
    25. 			swap(&a[parent], &a[child]);
    26. 			parent = child;
    27. 			child = parent * 2 + 1;
    28. 		}
    29. 		else
    30. 		{
    31. 			break;
    32. 		}
    33. 	}
    34. }
    35. //堆排序
    36. void HeapSort(int* a, int n)
    37. {
    38. 	//建堆 - 向下调整建堆
    39. 	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
    40. 	{
    41. 		AdjustDown(a, n, i);
    42. 	}
    43. 	int end = n - 1;
    44. 	while (end > 0)
    45. 	{
    46. 		swap(&a[0], &a[end]);
    47. 		AdjustDown(a, end, 0);
    48. 		end--;
    49. 	}
    50. }
    51.  
    52. int main()
    53. {
    54. 	int a[] = { 7,8,3,5,1,9,5,4 };
    55. 	HeapSort(a, sizeof(a) / sizeof(int));
    56. 	return 0;
    57. }

    代码中int i=(n-1-1)/2是通过孩子找父亲的下标，n是数组大小，先减一得到最后一个下标，再减一除以二得到最后一个孩子的父节点。 

    这就是向下调整建堆，以后我们用的都是向下调整建堆，不再使用向上调整建堆，这两种方式不仅代码量上有差距，时间复杂度上也有差距，向下调整建堆的时间复杂度更小。

    2. 两种建堆方式的时间复杂度比较

    2.1 向下调整建堆的时间复杂度

    前文中我们知道了，向下调整建堆要保证每个父节点的左右子树都是大堆（小堆），所以我们在调整的时候是从下往上进行的，而最后一层的每个叶节点本身就可以看做一个堆，不用调整，从它们的父节点开始调整（即倒数第二层开始调整），所以时间复杂度如下：

    总步数 = ∑（每一层的节点数*该节点需要调整的层数）

    2.2 向上调整建堆的时间复杂度

    向上调整和向下调整刚好相反，向下调整时，第h-1行的2^(h-2)个节点需向下调整1层，而向上调整时，第h-1行的2^(h-1)个节点需要向上调整h-2，向下调整是大乘小、小乘大，而向上调整时大乘大、小乘小，时间复杂度如下：

    以上就是向上调整建堆和向下调整建堆的时间复杂度，那我们整个堆排序的过程的时间复杂度是多少呢？

    堆排序过程中，除了建堆还有向下调整选数，当选数时，要首尾交换，交换一次，从头向下调整一次， 所以第h行的2^(h-1)个节点，每次首尾交换时都要调整(h-1)次，一共2^(h-1)*(h-1)，由此可见，选数据过程中的时间复杂度和向上调整建堆的时间复杂度保持一致，即为O(N*logN)

    所以堆排序整体的时间复杂度是：建堆+选数 = O(N+N*logN)，即O(N*logN)。

    Topk问题

    TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。
    比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
    对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：

    1. 用数据集合中前K个元素来建堆
    前k个最大的元素，则建小堆
    前k个最小的元素，则建大堆
    2. 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素
    将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。

    比如：我们要找10000个数中的前K个最小的数，就把先把前K个数建小堆，然后把用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素 

    代码如下：

    1. #define  _CRT_SECURE_NO_WARNINGS 1
    2. #include
    3. #include
    4. #include
    5.  
    6. //Top-K问题
    7. typedef int HeapDatatype;
    8.  
    9. swap(HeapDatatype* p1, HeapDatatype* p2)
    10. {
    11. 	HeapDatatype tmp = *p1;
    12. 	*p1 = *p2;
    13. 	*p2 = tmp;
    14. }
    15. //向下调整法
    16. void AdjustDown(HeapDatatype* a, int n, int parent)
    17. {
    18. 	int child = parent * 2 + 1;
    19. 	while (child < n)
    20. 	{
    21. 		if (child + 1 < n && a[child] > a[child + 1])
    22. 		{
    23. 			child++;
    24. 		}
    25. 		if (a[parent] > a[child])
    26. 		{
    27. 			swap(&a[parent], &a[child]);
    28. 			parent = child;
    29. 			child = parent * 2 + 1;
    30. 		}
    31. 		else
    32. 		{
    33. 			break;
    34. 		}
    35. 	}
    36. }
    37. void CreateNDate()
    38. {
    39. 	// 造数据
    40. 	int n = 10000;
    41. 	srand(time(0));
    42. 	const char* file = "data.txt";
    43. 	FILE* fin = fopen(file, "w");
    44. 	if (fin == NULL)
    45. 	{
    46. 		perror("fopen error");
    47. 		return;
    48. 	}
    49.  
    50. 	for (size_t i = 0; i < n; ++i)
    51. 	{
    52. 		int x = rand() % 1000000;
    53. 		fprintf(fin, "%d\n", x);
    54. 	}
    55.  
    56. 	fclose(fin);
    57. }
    58.  
    59. void PrintTopK(int k)
    60. {
    61. 	const char* file = "data.txt";
    62. 	FILE* fout = fopen(file, "r");
    63. 	if (fout == NULL)
    64. 	{
    65. 		perror("fopen error");
    66. 		return;
    67. 	}
    68.  
    69. 	int* kminheap = (int*)malloc(sizeof(int) * k);
    70. 	if (kminheap == NULL)
    71. 	{
    72. 		perror("malloc error");
    73. 		return;
    74. 	}
    75.  
    76. 	for (int i = 0; i < k; i++)
    77. 	{
    78. 		fscanf(fout, "%d", &kminheap[i]);
    79. 	}
    80.  
    81. 	// 建小堆
    82. 	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
    83. 	{
    84. 		AdjustDown(kminheap, k, i);
    85. 	}
    86.  
    87. 	int val = 0;
    88. 	while (!feof(fout))
    89. 	{
    90. 		fscanf(fout, "%d", &val);
    91. 		if (val > kminheap[0])
    92. 		{
    93. 			kminheap[0] = val;
    94. 			AdjustDown(kminheap, k, 0);
    95. 		}
    96. 	}
    97.  
    98. 	for (int i = 0; i < k; i++)
    99. 	{
    100. 		printf("%d ", kminheap[i]);
    101. 	}
    102. 	printf("\n");
    103. }
    104.  
    105.  
    106. int main()
    107. {
    108. 	CreateNDate();
    109. 	PrintTopK(5);
    110. 	return 0;
    111. }

    关于堆排序的所有内容已经学完了，下节我们继续讲二叉树的前序、中序、后序和层序。

    未完待续。。。

  • 相关阅读:
    五子棋AI算法和开局定式（直指13式）破解
    微信网站登录功能
    金九银十进大厂必刷的105道Java面试题（不得不说的秘密）
    小红书达人怎么对接，博主沟通流程汇总！
    Spring Boot - filter 的顺序
    小程序原生开发中的onLoad和onShow
    最简单的git图解（git stash）
    day31 代码随想录 分发饼干&摆动序列&最大子序和
    IO进线程：信号灯
    动手学深度学习_个人笔记_李沐（更新中......）
  • 原文地址：https://blog.csdn.net/syh163/article/details/134383449