def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2
 
    if left < n and arr[left] > arr[largest]:
        largest = left
 
    if right < n and arr[right] > arr[largest]:
        largest = right
 
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)
 
 
def build_heap(arr):
    n = len(arr)
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
 
 
def heap_sort(arr):
    n = len(arr)
 
    build_heap(arr)
 
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)
 
 
if __name__ == "__main__":
    arr = [5, 10, 264, 362, 865, 63, 94, 475, 135, 932,
           25, 9, 33, 287, 332, 745, 377, 820, 62, 1]
 
    # 1. 힙 생성 결과 출력
    heap_arr = arr[:]
    build_heap(heap_arr)
    print("1. 생성된 힙 배열:", heap_arr)
 
    # 2. 힙 정렬 결과 출력
    sorted_arr = arr[:]
    heap_sort(sorted_arr)
    print("2. 정렬된 배열:", sorted_arr)
 

ZGVmIGhlYXBpZnkoYXJyLCBuLCBpKToKICAgIGxhcmdlc3QgPSBpCiAgICBsZWZ0ID0gMiAqIGkgKyAxCiAgICByaWdodCA9IDIgKiBpICsgMgoKICAgIGlmIGxlZnQgPCBuIGFuZCBhcnJbbGVmdF0gPiBhcnJbbGFyZ2VzdF06CiAgICAgICAgbGFyZ2VzdCA9IGxlZnQKCiAgICBpZiByaWdodCA8IG4gYW5kIGFycltyaWdodF0gPiBhcnJbbGFyZ2VzdF06CiAgICAgICAgbGFyZ2VzdCA9IHJpZ2h0CgogICAgaWYgbGFyZ2VzdCAhPSBpOgogICAgICAgIGFycltpXSwgYXJyW2xhcmdlc3RdID0gYXJyW2xhcmdlc3RdLCBhcnJbaV0KICAgICAgICBoZWFwaWZ5KGFyciwgbiwgbGFyZ2VzdCkKCgpkZWYgYnVpbGRfaGVhcChhcnIpOgogICAgbiA9IGxlbihhcnIpCiAgICBmb3IgaSBpbiByYW5nZShuIC8vIDIgLSAxLCAtMSwgLTEpOgogICAgICAgIGhlYXBpZnkoYXJyLCBuLCBpKQoKCmRlZiBoZWFwX3NvcnQoYXJyKToKICAgIG4gPSBsZW4oYXJyKQoKICAgIGJ1aWxkX2hlYXAoYXJyKQoKICAgIGZvciBpIGluIHJhbmdlKG4gLSAxLCAwLCAtMSk6CiAgICAgICAgYXJyWzBdLCBhcnJbaV0gPSBhcnJbaV0sIGFyclswXQogICAgICAgIGhlYXBpZnkoYXJyLCBpLCAwKQoKCmlmIF9fbmFtZV9fID09ICJfX21haW5fXyI6CiAgICBhcnIgPSBbNSwgMTAsIDI2NCwgMzYyLCA4NjUsIDYzLCA5NCwgNDc1LCAxMzUsIDkzMiwKICAgICAgICAgICAyNSwgOSwgMzMsIDI4NywgMzMyLCA3NDUsIDM3NywgODIwLCA2MiwgMV0KCiAgICAjIDEuIO2emSDsg53shLEg6rKw6rO8IOy2nOugpQogICAgaGVhcF9hcnIgPSBhcnJbOl0KICAgIGJ1aWxkX2hlYXAoaGVhcF9hcnIpCiAgICBwcmludCgiMS4g7IOd7ISx65CcIO2emSDrsLDsl7Q6IiwgaGVhcF9hcnIpCgogICAgIyAyLiDtnpkg7KCV66CsIOqysOqzvCDstpzroKUKICAgIHNvcnRlZF9hcnIgPSBhcnJbOl0KICAgIGhlYXBfc29ydChzb3J0ZWRfYXJyKQogICAgcHJpbnQoIjIuIOygleugrOuQnCDrsLDsl7Q6Iiwgc29ydGVkX2FycikK