当前位置:   article > 正文

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

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

闽ICP备14008679号