Python 堆排序

"""

Author: OhiyoX
Date: 2020-02-03


"""

def swap(tree, i, j):
    temp=tree[i]
    tree[i] = tree[j]
    tree[j] = temp


def heapify(tree, n, i):
    """
    To heapify the single heap
    n indicates how many nodes, i is location
    """
    if i >= n:
        return
    c1 = 2 * i + 1  # left node
    c2 = 2 * i + 2  # right node
    max = i
    if c1 < n and tree[c1] > tree[i]:
        max = c1
    if c2 < n and tree[c2] > tree[max]:
        max = c2
    if max != i:
        swap(tree, max, i)


def build_heap(tree, n):
    """build heap"""
    last_node = n-1  # last node
    parent = (last_node - 1) // 2  # last node's parent node
    for i in range(parent, -1, -1):
        heapify(tree, n, i)


def heap_sort(tree, n):
    build_heap(tree, n)
    for i in range(n-1, -1, -1):
        swap(tree, i, 0)
        build_heap(tree, i)


"""main"""
tree = [10, 6, 3, 2, 0, 4, 1, 7, 5, 8, 9]
n = len(tree)
heap_sort(tree, n)
show = ''
for i in range(n):
    show = show + str(tree[i]) + " "

print(show)