# ヒープソート

import math

def exchange(A, x, y):
    """配列Aのx番目とy番目の要素の値を入れ替える [cite: 86]"""
    A[x], A[y] = A[y], A[x]

def heap_correct(A, i, length):
    """
    ノードiを根とする部分木をヒープ条件に適合させる [cite: 40, 90]
    ※Pythonの0-indexに合わせて調整
    """
    largest = i
    l_child = 2 * i + 1  # 左の子のインデックス
    r_child = 2 * i + 2  # 右の子のインデックス

    # 左の子と比較 [cite: 94, 95]
    if l_child < length and A[l_child] > A[largest]:
        largest = l_child

    # 右の子と比較 [cite: 100, 104]
    if r_child < length and A[r_child] > A[largest]:
        largest = r_child

    # 最大値が親でない場合、入れ替えて再帰呼び出し [cite: 106, 107, 108]
    if largest != i:
        exchange(A, i, largest)
        heap_correct(A, largest, length)

def heap_make(A):
    """
    二分木をヒープに変換する [cite: 112, 113]
    """
    length = len(A)
    # 最後の親ノードから根に向かって順に処理 [cite: 114, 115]
    # floor(15 / 2) = 7 番目 (0-indexでは index 6) から開始 
    start_node = (length // 2) - 1
    
    for i in range(start_node, -1, -1):
        heap_correct(A, i, length)

# 図6の二分木データ (ノード番号順) [cite: 124, 156]
# index: 0  1  2  3   4  5  6   7  8   9  10 11 12 13 14
# node:  1  2  3  4   5  6  7   8  9  10  11 12 13 14 15
B = [5, 2, 10, 14, 9, 12, 6, 3, 11, 21, 1, 4, 17, 15, 14]

print("変換前:", B)
heap_make(B)
print("変換後:", B)
print("根の値 (最大値):", B[0])