堆排序+代码(通俗易懂简洁扼要多方法)

原文出处 https://zhuanlan.zhihu.com/p/361159875?

top-k问题中，当快速排序因原数组高度有序明显退化时，切换到堆排序是解决效率最高的方法之一

时间复杂度：最坏情况下O(nlogn)

空间复杂度：O(1)

缺点：不稳定排序

 arr = [2,5,7,2,7,4,8,9,3,9,54,2,3,45,2,15,16,18]

方法A

从最后一个parent节点倒叙遍历直到根节点，每遍历一个parent和他的两个child: c1,c2进行比较，交换，保证最大/最小的节点在parent位置，如进行过交换操作，则以被交换子节点为输入参数递归执行heapify

def solution(arr):
    n = len(arr)
    build_heap(arr, n)
    print(arr)

def build_heap(arr, n):
    last_node = n - 1
    parent = (last_node-1) // 2
    for i in range(parent, -1, -1):
        heapify(arr, n, i)

def heapify(arr, n, i):
    # 对第i个节点进行heapify, 大顶堆
    if i >= n:
        return
    c1 = 2 * i + 1
    c2 = 2 * i + 2
    maxvalue = i
    if c1 < n and arr[c1] > arr[maxvalue]:
        maxvalue = c1
    if c2 < n and arr[c2] > arr[maxvalue]:
        maxvalue = c2
    if maxvalue != i:
        arr[maxvalue], arr[i] = arr[i], arr[maxvalue]
        heapify(arr, n, maxvalue)

def heapify_2(arr, n, i):
    # 对第i个节点进行heapify, 小顶堆
    if i >= n:
        return
    c1 = 2 * i + 1
    c2 = 2 * i + 2
    minvalue = i
    if c1 < n and arr[c1] < arr[minvalue]:
        minvalue = c1
    if c2 < n and arr[c2] < arr[minvalue]:
        minvalue = c2
    if minvalue != i:
        arr[minvalue], arr[i] = arr[i], arr[minvalue]
        heapify_2(arr, n, minvalue)

方法B

遍历所有节点，每遍历一个节点与他的parent：arr[(index-1) // 2]进行比较，交换，保证较大/较小的节点在parent位置，如进行过交换操作，则index变为被交换的parent继续进入循环判断（本质上也是一种递归，等价于递归执行heapify）

def solution2(arr):
    heapsort(arr, len(arr))
    print(arr)

def heapsort(arr, n):
    # 从孩子节点开始和父母比大小, 大顶堆
    for index in range(1, n):
        while arr[(index-1) // 2] < arr[index] and index > 0:
            arr[(index-1) // 2], arr[index] = arr[index], arr[(index-1) // 2]
            index = (index-1) // 2
        return arr

def heapsort_2(arr, n):
    # 从孩子节点开始和父母比大小, 小顶堆
    for index in range(1, n):
        while arr[(index-1) // 2] > arr[index] and index > 0:
            arr[(index-1) // 2], arr[index] = arr[index], arr[(index-1) // 2]
            index = (index-1) // 2
        return arr

时间复杂度分析

遍历节点的时间复杂度为O(n)这个任何情况下都不会有波动，但是递归执行heapify的时候即使从头到尾递归，时间复杂度也不超过O(logn)，更何况在刚好满足大小顶堆条件的情况下，每次比较，不交换，时间复杂度会下降为O(1)，所以堆排序的时间复杂度始终小于等于O(nlogn)。准确地说是介于O(n)和O(nlogn)之间。

github代码出处：https://github.com/stevezkw1998/common-algorithm-demos/blob/master/heapsort.py

欢迎关注我的github：stevezkw1998 - Overview