ALDS1_9_B: Maximum Heap

適当に数字を並べた配列を並べ替えてmax-ヒープを作ります
アルゴリズムは書いてあるのでコードにするだけ
自分で考え出せるかというとそれはまた別の話

def heap_size(A):
    return len(A) - 1

def max_heapify(A, i):
    l = left_node(i)
    r = right_node(i)

    if l <= heap_size(A) and A[l] > A[i]:
        largest = l
    else:
        largest = i
    if r <= heap_size(A) and A[r] > A[largest]:
        largest = r

    if largest != i:
        swap(A, i, largest)
        max_heapify(A, largest)

def build_max_heap(A):
    for i in reversed(range(1, heap_size(A) // 2 + 1)):
        max_heapify(A, i)

def print_heap(A):
    for i in range(1, heap_size(A) + 1):
        print(" {}".format(A[i]), end="")
    print()

def main():
    _ = int(input())
    A = [None] + [int(x) for x in input().split()]

    build_max_heap(A)
    print_heap(A)

コードを書いただけだとあまりピンとこない
図を描いてみたらピンと来た
build_max_heapでH/2から始めてるのは、下から２段めってことか

役に立つ図ではないけど