堆排序(Heap Sort)

堆是一个数组，可以将其视为一个近似的完全二叉树。换言之，即将一维的数组以二维的二叉树结构形式来对待处理。

思想

在递增排序中，利用最大堆根节点为最大值的性质，每次取最大堆的根节点元素放到数组末尾，以此前推形成递增排序结果。

• 首先构造初始最大堆
• 交换最大堆的根节点元素与堆尾元素
• 缩小堆规模
• 重新调整最大堆

时间复杂度: O(nlogn)

构造初始最大堆时间复杂度为O(n)，每次重整最大堆的时间复杂度为O(logn)，n-1次重整最大堆时间复杂度为O(nlogn)，总时间复杂度为O(n)+O(nlogn)即为O(nlogn)。

代码实现

#############
#
# Heap Sort
#
#############

def reconstruct_max_heap(array, end, root):
    """
    :param array: list
    :param end: int, the heap last node pos
    :param root: int, heap root 
    :return: None
    """
    left_sub_root = root * 2
    right_sub_root = root * 2 + 1
    largest = root

    if left_sub_root <= end and array[left_sub_root] > array[root]:
        largest = left_sub_root

    if right_sub_root <= end and array[right_sub_root] > array[largest]:
        largest = right_sub_root

    if largest != root:
        array[root], array[largest] = array[largest], array[root]
        reconstruct_max_heap(array, end, largest)


def build_max_heap(array):
    """
    :param array: list
    :return: list
    """
    # Reconstruct sub max heap from the last non-leaf-node and back towards the root.
    n = len(array)
    cur = n // 2
    
    while cur >= 0:
        reconstruct_max_heap(array, n-1, cur)
        cur -= 1

    return array

def heap_sort(array):
    """
    Ascending order sort.
    :param array: list
    :return: list
    """
    # Build an initial max-heap.
    build_max_heap(array)

    end = len(array) - 1
    while end >= 1:
        # Exchange root node and tail node.
        array[0], array[end] = array[end], array[0]

        # Decrease the max-heap size.
        end -= 1

        # Reconstruct max-heap.
        reconstruct_max_heap(array, end, 0)

    return array


if __name__ == "__main__":
    li = [5, 13, 2, 25, 7, 17, 20, 8, 4]
    heap_sort(li)
    print(li)