『Heapsort』详解「堆排序」的Python实现
hokyo
发布于 4 年, 8 ヶ月 之前
3724
堆排序
上一篇推荐阅读:『二叉树』详解「广度遍历・深度遍历」的Python实现
1 什么是堆
堆结构有很多种，如二叉堆、B堆、斐波那契堆、三元堆，树堆、弱堆等。
二叉堆是堆实现中最流行的一种。二叉堆是一个完全二叉树，树的所有内部节点都被完全填充，最后一层可以完全填充的或部分填充。通俗的说，堆（二叉堆）可以视为一棵完全的二叉树。完全二叉树的一个优秀的性质就是，除了最底层之外，每一层都是满的。堆又分为最大堆（堆顶Root是最大值）和最小堆（堆顶Root是最小值）。
总结一下。只要你是一个完全二叉树，父节点又大于子节点，你就是堆。
完全二叉树 + 父节点大于(或小于)子节点 = 堆
1-1. 分析堆的规律
# 最大堆 父节点 大于 子节点 30(0) / \ 25(1) 10 (2) / \ / \ 20(3) 8(4) 6(5) 2(6) # 最小堆 父节点 小于 子节点 10(0) / \ 40(1) 15 (2) / \ / \ 45(3) 50(4) 18(5) 19(6)
父节点为0，左子节点1，右子节点2。
父节点为1，左子节点3，右子节点4。
父节点为2，左子节点5，右子节点6。
父节点为3，左子节点7，右子节点8。
......
父节点为i，左子节点2i＋1，右子节点2i＋2。
反过来当你知道子节点为i的时候，那么父节点就是(i-1)/2
1-2 堆化(heapify)
由上面的堆的规律，我们就可以随便把一个列表给用堆的形式表现出来。(不是排序！)
比如我们现在有一个这样的一组列表。list = [4, 10, 3, 5, 1, 2]
这个列表目前不是一个堆，只是一个错乱的数组。
按照从上到下，从左到右画出来是这样的。
# 但这并不是一个堆 # 堆必须要所有父节点大于(小于)子节点，于是我们要通过堆化把她变成右边的样子。 # 堆化前 4(0) / \ 10(1) 3(2) / \ / 5(3) 1(4) 2(5) # 堆化后(最大堆) 10(0) / \ 5(1) 3(2) / \ / 4(3) 1(4) 2(5)
1-3 堆化代码实现
遵循原则
- 遍历所有父节点
- 比较所有节点，最大给父节点
- 递归成型
""" arr:需要排序的列表 n：列表长度 i：开始节点 """ def heapify(arr: list, n: int, i: int) -> list: # 递归条件 if i >= n: return # 默认父节点最大index largest = i # 左节点index lchild = 2 * i + 1 # 右节点index rchild = 2 * i + 2 # 如果左节点小于整个节点长度，并且左节点大于父节点 # 那么index交换 if lchild < n and arr[i] < arr[lchild]: largest = lchild # 如果右节点小于整个节点长度，并且右节点大于父节点 # 那么index交换 if rchild < n and arr[i] < arr[rchild]: largest = rchild # 如果父节点已经为最大值了，那么就不用交换，否则进行交换 if largest != i: arr[i], arr[largest] = arr[largest], arr[i] # 进行递归，递归条件就是i >= n: # 因为节点是不可能大于整个列表的最大长度的 heapify(arr, n, largest) arr = [4,10,3,5,1,2] print('----heapify前-----') print(arr) n = len(arr) # 此处我设置为root节点的index:0开始 heapify(arr, n ,0) print('----heapify后-----') print(arr) # result # ----heapify前----- # [4, 10, 3, 5, 1, 2] # ----heapify后----- # [10, 5, 3, 4, 1, 2]
上面我们可以看到
即使堆化后也不是一个排序好的列表。
但确是一个最大堆！
2. 堆排序实现
什么是堆排序呢。就是利用堆的数据结构特性来进行排序算法。
至于堆有什么特性呢。就是堆化之后最大值or最小值可以找出来的特性。
我们上面解决了堆化的问题，但并没有解决排序的问题。
参考链接:图解堆排序。画的很透彻的图。建议阅读。
步骤有3个。创建堆，调整堆，堆排序。
白话文版本。堆化（最大堆） + 选择排序 = 堆排序
脑海蓝图code版本。未排序 list = [5,8,2,33,19,1,6]→堆化成堆→已排序完成 list = [1, 2, 5, 6, 8, 19, 33]
Q：为什么要堆化？
堆化可以保证最顶上的Root结点是最大值or最小值。
Q：为什么要调整？
每一次堆化之后，把最大值or最小值拿出来一个个排序（类似于选择排序）这不就可以堆排序了吗？
Python代码实现走起。
def heapify(arr, n, i): # 递归条件出口 if i >= n : return # 默认i为最大 largest = i lchild = 2 * i + 1 rchild = 2 * i + 2 if lchild < n and arr[largest] < arr[lchild]: largest = lchild if rchild < n and arr[largest] < arr[rchild]: largest = rchild if largest != i: arr[i], arr[largest] = arr[largest], arr[i] # 递归，从节点开始 heapify(arr, n, largest) def heap_sort(arr): n = len(arr) # 从后向前直到index为0 for i in range(n, -1, -1): # n是长度不会变，i是从最后一个节点一直到index为0 heapify(arr, n, i) # 这个为什么是n-1，是因为这个n-1代表最后一个堆的index for i in range(n-1, 0, -1): arr[0], arr[i], = arr[i], arr[0] # 这里为什么是i在这里，是因为长度是随着每次交换最后1个，长度就减1，一直到0 heapify(arr, i, 0) arr = [5, 8, 2, 33, 19, 1, 6] heap_sort(arr) print(arr) # result # [1, 2, 5, 6, 8, 19, 33]
代码很长，注释可能会影响可读性。
剩下的明天起床写吧。
结论（个人心得）
等我在写一遍在写心得吧。
共有评论(0)