...

『Heapsort』详解「堆排序」的Python实现

堆排序

上一篇推荐阅读:『二叉树』详解「广度遍历・深度遍历」的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. 堆排序实现

什么是堆排序呢。就是利用堆的数据结构特性来进行排序算法。
我们上面解决了堆化的问题,但并没有解决排序的问题。
参考链接:图解堆排序。画的很透彻的图。建议阅读。

步骤有3个。创建堆,调整堆,堆排序。
白话文版本。堆化 + 选择排序 = 堆排序
脑海蓝图code版本。

❶ 未排序list = [5,8,2,33,19,1,6] ❷ 堆化成堆 ❸ 已排序完成 list = [1, 2, 5, 6, 8, 19, 33]

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)

登陆即可评论哦