def sort(A):
    construct_heap(A, 0, len(A)-1);print(A)
    select_max(A, len(A) - 1)

left  = lambda n: 2 * n + 1
right = lambda n: 2 * n + 2

def construct_heap(A, n, last):
    if last < left(n):
        return
    construct_heap(A, left(n), last)
    if right(n) <= last:
        construct_heap(A, right(n), last)
    print(A);exchange_nodes(A, n, last)

def select_max(A, last):
    if last < 1:
        return
    A[0], A[last] = A[last], A[0];print(A)
    exchange_nodes(A, 0, last - 1);print(A)
    select_max(A, last - 1)

def exchange_nodes(A, n, last):
    if last < left(n):
        return
    child = left(n)
    if right(n) <= last and A[left(n)] < A[right(n)]:
        child = right(n)
    if A[n] < A[child]:
        A[n], A[child] = A[child], A[n];print(A)
        exchange_nodes(A, child, last)
