#!/usr/bin/python
# -*- coding: UTF-8 -*-


# 是否倒序
r = False


# 下沉
def sink(a, i, n):
    while i * 2 + 1 <= n:
        j = i * 2 + 1
        if j + 1 <= n and compare(a, j + 1, j):
            j += 1
        if compare(a, j, i):
            swap(a, i, j)
            i = j
        else:
            break


def compare(a, i, j):
    return a[i] > a[j] if not r else a[i] < a[j]


def swap(a, i, j):
    t = a[i]
    a[i] = a[j]
    a[j] = t


def init(a):
    le = len(a)
    ei = le - 1
    si = le / 2 - 1
    while si >= 0:
        sink(a, si, ei)
        si -= 1


def adjust(a):
    ei = len(a) - 1
    while ei > 0:
        swap(a, 0, ei)
        ei -= 1
        sink(a, 0, ei)


def heap_sort(a):
    init(a)
    adjust(a)
    print a


heap_sort([3, 1, 2, 5, 6, 9, 6, 0, 4, 0])