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

【数据结构】——堆排序_python 堆排序(topk问题)

作者：知新_RL | 2024-07-17 16:25:51

赞

踩

python 堆排序(topk问题)

目录

一、视频链接：

二、随笔笔记

 三、代码实现（构造堆、向下调整）自定义+内置函数

四、堆排序之topk问题的应用

一、视频链接：

https://www.bilibili.com/video/BV1mp4y1D7UP?p=19

https://www.bilibili.com/video/BV1mp4y1D7UP?p=20

https://www.bilibili.com/video/BV1mp4y1D7UP?p=21

https://www.bilibili.com/video/BV1mp4y1D7UP?p=22

https://www.bilibili.com/video/BV1mp4y1D7UP?p=23

...

https://www.bilibili.com/video/BV1mp4y1D7UP?p=29

二、随笔笔记

 

 

 

 

 三、代码实现（构造堆、向下调整）自定义+内置函数

  1. '''
  2. 堆排序
  3. 排序过程：
  4. 1、构造堆，使得整个二叉树是一个堆
  5. 2、挨个出数，首先得到堆顶的元素，堆顶元素是第一大元素
  6. 3、堆顶元素出数后，位置空出来了，将堆的最后一个元素放在堆顶，然后进行向下调整，使得堆再次有序
  7. 4、此时堆顶的元素是第二大元素
  8. 5、重复3，直到堆空，堆排序完成
  9. '''
  10.  
  11. # 向下调整函数，前提是堆顶结点的左右子树已经是有序的大根堆
  12. def sift(li,low,high):
  13. 	'''
  14. 	这里以大根堆为例，通过向下调整来使得堆有序，父节点比两个子节点元素大,主要思想是通过比较根节点和两个子节点的
  15. 	大小来进行调整，使得子节点总是小于其直接父节点
  16. 	:param li: 列表
  17. 	:param low: 堆顶位置
  18. 	:param high: 堆最后一个元素的位置
  19. 	:return: 没有返回值，直接生成的是一个有序的堆，以列表1形式呈现
  20. 	'''
  21. 	tmp = li[low] # 堆顶元素
  22. 	i = low # 堆顶元素的位置
  23. 	j = 2 * i + 1 # 根节点i的左子节点位置
  24. 	while j <= high: # 保证有子节点
  25. 		# 首先比较两个左右两个子节点的大小，将更大的子节点元素和父节点进行比较
  26. 		if j+1 <= high and li[j] < li[j+1]: # 右子节点存在（j+1<high)并且右子节点更大
  27. 			j = j + 1 # 将j设置为节点大的那个位置
  28. 		#将更大子节点元素和父节点元素进行比较
  29. 		if tmp < li[j]: #父节点元素小于更大子节点元素
  30. 			li[i] = li[j] # 将大的子节点元素赋值给父节点
  31. 			i = j # 往下一层进行调整
  32. 			j = 2 * i + 1 # 更新j为新的父节点的左子节点
  33. 		# 如果父节点比更大的子节点元素还要大的话，那就说明已经使堆有序化了，
  34. 		# 注意这里的前提是父节点的左右子树已经是有序的大根堆，因此当父节点不小于子节点时，就完成了堆有序化
  35. 		else:
  36. 			li[i] = tmp # 将当前的位置赋值为tmp的值
  37. 			break # 因为存在j还没有到最后就完成了堆排序，这时候可以直接跳出循环
  38. 	else: # 当不存在子节点时，说明完成了堆有序化，这时候将tmp赋值给最后一个节点
  39. 		li[i] = tmp
  40.  
  41. # 构建堆的函数，将堆构建成一个大根堆，注意这里的大根堆是完全二叉树
  42. def creatHeap(li):
  43. 	'''
  44. 	这是对无序的完全二叉树进行有序化，使得完全二叉树成为特殊的完全二叉树，这里以大根堆为例
  45. 	:param li: 列表
  46. 	:return: 无返回值，直接对li进行了构建，因为列表是引用的方式进行访问的，所以不需要返回列表调用函数后也发生了改变
  47. 	'''
  48. 	heapLen = len(li) # 堆的元素个数，这里指的是列表的长度
  49. 	# (heapLen - 2) // 2这里指的是通过子节点来获得父节点的方法，//是指取整
  50. 	for rootNode in range((heapLen - 2) // 2,-1,-1): # 这里指的是遍历所有的根节点，然后对每一个根节点的子树进行有序化，向下调整
  51. 		sift(li,rootNode,heapLen - 1)
  52.  
  53. # 堆排序
  54. def heapSorted1(li):
  55. 	'''
  56. 	这个函数是自定义的函数
  57. 	主要思想：对大根堆进行排序，首先high指的是树的最后一个位置，在这里也指的是未排序区的最后一个位置
  58. 	先对树进行堆的有序化，然后交换堆顶和high位置的元素，此时high的位置向前进一个位置，直到high的位置为0
  59. 	时，说明此时未排序的元素就一个元素了，也就是完成了堆排序
  60. 	:param li: 列表
  61. 	:return: 
  62. 	'''
  63. 	creatHeap(li) # 得到大根堆
  64. 	heapLen = len(li) # 获得元素的个数
  65. 	high = heapLen - 1 # 未排序的最后一个元素的位置
  66. 	low = 0 # 堆顶位置
  67. 	while high != 0: # 当未排序的索引为0时，说明只是剩下一个元素，排序完成
  68. 		li[low],li[high] = li[high],li[low] # 堆顶和未排序最后一个元素进行合并
  69. 		high -= 1 # 未排序区缩小一个位置
  70. 		sift(li,low,high) # 对新的堆进行有序化
  71.  
  72. def heapSorted2(li):
  73. 	'''
  74. 	路飞思想：语言更简洁，但是个人觉得可读性不太好，不如上面的编程
  75. 	:param li: 列表
  76. 	:return: 
  77. 	'''
  78. 	creatHeap(li)  # 得到大根堆
  79. 	heapLen = len(li)  # 获得元素的个数
  80. 	for i in range(heapLen-1,-1,-1):
  81. 		# i表示当前的堆的最后一个位置
  82. 		li[0],li[i] = li[i],li[0]
  83. 		sift(li,0,i - 1)
  84.  
  85. def sysFun(li):
  86. 	'''
  87. 	这里使用了Python内置模块
  88. 	:param li: 列表
  89. 	:return: 
  90. 	'''
  91. 	import heapq # 这个实现的是小根堆
  92. 	heapq.heapify(li) # 构建小根堆
  93. 	liSorted = []
  94. 	for i in range(len(li)):
  95. 		popEle = heapq.heappop(li) # 每次弹出最小的元素
  96. 		liSorted.append(popEle) # 将弹出的元素加入到列表中，得到的就是排好序的列表（从小到大排序）
  97. 	return liSorted
  98.  
  99. if __name__ == '__main__':
  100. 	import random
  101. 	li1 = list(range(20)) # 随机生成20个数
  102. 	li2 = list(range(20)) # 随机生成20个数
  103. 	li3 = list(range(20)) # 随机生成20个数
  104. 	random.shuffle(li1) # 打乱
  105. 	random.shuffle(li2) # 打乱
  106. 	random.shuffle(li3) # 打乱
  107. 	print(li1,"打乱后待排序的列表1")
  108. 	print(li2,"打乱后待排序的列表2")
  109. 	print(li3,"打乱后待排序的列表3")
  110. 	print("-------------------------------------------------------------------------")
  111. 	heapSorted1(li1)
  112. 	print(li1,"自己的代码")
  113. 	print("-------------------------------------------------------------------------")
  114. 	heapSorted2(li2)
  115. 	print(li2,"路飞的代码")
  116. 	print("-------------------------------------------------------------------------")
  117. 	liSorted = sysFun(li3)
  118. 	print(liSorted,"python内置模板")
'
运行

[18, 5, 0, 3, 7, 11, 1, 6, 16, 10, 2, 14, 17, 8, 19, 12, 13, 4, 9, 15] 打乱后待排序的列表1
[16, 19, 18, 15, 11, 12, 5, 2, 6, 9, 10, 0, 1, 14, 8, 7, 13, 4, 17, 3] 打乱后待排序的列表2
[9, 11, 12, 16, 14, 3, 19, 6, 0, 5, 15, 8, 2, 1, 7, 13, 18, 17, 10, 4] 打乱后待排序的列表3
-------------------------------------------------------------------------
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] 自己的代码
-------------------------------------------------------------------------
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] 路飞的代码
-------------------------------------------------------------------------
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] python内置模板

四、堆排序之topk问题的应用

  1. '''
  2. topk问题就是从n个数中取得前面k个大（小）的数
  3. '''
  4.  
  5. # 小根堆的向下调整方法
  6. # 向下调整函数，前提是堆顶结点的左右子树已经是有序的小根堆
  7. def sift(li,low,high):
  8. 	'''
  9. 	这里以小根堆为例，通过向下调整来使得堆有序，父节点比两个子节点元素小,主要思想是通过比较根节点和两个子节点的
  10. 	大小来进行调整，使得子节点总是大于其直接父节点
  11. 	:param li: 列表
  12. 	:param low: 堆顶位置
  13. 	:param high: 堆最后一个元素的位置
  14. 	:return: 没有返回值，直接生成的是一个有序的堆，以列表1形式呈现
  15. 	'''
  16. 	tmp = li[low] # 堆顶元素
  17. 	i = low # 堆顶元素的位置
  18. 	j = 2 * i + 1 # 根节点i的左子节点位置
  19. 	while j <= high: # 保证有子节点
  20. 		# 首先比较两个左右两个子节点的大小，将更小的子节点元素和父节点进行比较
  21. 		if j+1 <= high and li[j] > li[j+1]: # 右子节点存在（j+1<high)并且右子节点更小
  22. 			j = j + 1 # 将j设置为节点小的那个位置
  23. 		#将更小子节点元素和父节点元素进行比较
  24. 		if tmp > li[j]: #父节点元素小于更小子节点元素
  25. 			li[i] = li[j] # 将小的子节点元素赋值给父节点
  26. 			i = j # 往下一层进行调整
  27. 			j = 2 * i + 1 # 更新j为新的父节点的左子节点
  28. 		# 如果父节点比更小的子节点元素还要小的话，那就说明已经使堆有序化了，
  29. 		# 注意这里的前提是父节点的左右子树已经是有序的小根堆，因此当父节点不大于子节点时，就完成了堆有序化
  30. 		else:
  31. 			li[i] = tmp # 将当前的位置赋值为tmp的值
  32. 			break # 因为存在j还没有到最后就完成了堆排序，这时候可以直接跳出循环
  33. 	else: # 当不存在子节点时，说明完成了堆有序化，这时候将tmp赋值给最后一个节点
  34. 		li[i] = tmp
  35.  
  36. def creatHeap(li):
  37. 	'''
  38. 	这是对无序的完全二叉树进行有序化，使得完全二叉树成为特殊的完全二叉树，这里以小根堆为例
  39. 	:param li: 列表
  40. 	:return: 无返回值，直接对li进行了构建，因为列表是引用的方式进行访问的，所以不需要返回列表调用函数后也发生了改变
  41. 	'''
  42. 	heapLen = len(li) # 堆的元素个数，这里指的是列表的长度
  43. 	# (heapLen - 2) // 2这里指的是通过子节点来获得父节点的方法，//是指取整
  44. 	for rootNode in range((heapLen - 2) // 2,-1,-1): # 这里指的是遍历所有的根节点，然后对每一个根节点的子树进行有序化，向下调整
  45. 		sift(li,rootNode,heapLen - 1)
  46.  
  47. def heapSorted2(li):
  48. 	'''
  49. 	路飞思想：语言更简洁，但是个人觉得可读性不太好
  50. 	:param li: 列表
  51. 	:return: 
  52. 	'''
  53. 	creatHeap(li)  # 得到小根堆
  54. 	heapLen = len(li)  # 获得元素的个数
  55. 	for i in range(heapLen-1,-1,-1):
  56. 		# i表示当前的堆的最后一个位置
  57. 		li[0],li[i] = li[i],li[0]
  58. 		sift(li,0,i - 1)
  59.  
  60. def topkPro(li,k):
  61. 	'''
  62. 	从列表中取前k个大的数字
  63. 	:param li: 列表
  64. 	:param k: 需要取的元素个数
  65. 	:return: 返回的是列表中最大的前k个数，但是不一定有序，如果要拍好序，可以在调用一次堆排序函数
  66. 	'''
  67. 	liK = li[0:k] # 取前k个数
  68. 	sift(liK,0,k-1) # 对前k个数构建小根堆
  69. 	for index in range(k,len(li)): # 遍历循环不在堆里的元素
  70. 		if li[index] > liK[0]: # 比较与堆顶元素的大小
  71. 			liK[0] = li[index] # 若比堆顶元素大则替换堆顶元素
  72. 			sift(liK,0,k-1) # 重新构建小根堆
  73. 	heapSorted2(liK) # 对最后得到的k各元素进行排序
  74. 	return liK
  75.  
  76. if __name__ == '__main__':
  77. 	import random
  78. 	li = list(range(20)) # 随机生成20个数
  79. 	random.shuffle(li) # 打乱
  80. 	print(li,"未排序的列表")
  81. 	print("---------------------------------------")
  82. 	heapSorted2(li)
  83. 	print(li,"堆排序后的列表")
  84. 	print("----------------------------------------")
  85. 	liK = topkPro(li,5)
  86. 	print(liK,"li列表中前k大的数")
'
运行

[19, 18, 3, 15, 6, 4, 17, 7, 8, 9, 12, 5, 13, 14, 16, 0, 1, 2, 10, 11] 未排序的列表
---------------------------------------
[19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0] 堆排序后的列表
----------------------------------------
[19, 18, 17, 16, 15] li列表中前k大的数

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

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

  

闽ICP备14008679号