def heapify(arr, n, i):
    """arr[0..n-1] 범위에서 i를 루트로 하는 서브트리를 힙으로 만듦"""
    largest = i       # 루트
    left = 2 * i + 1  # 왼쪽 자식
    right = 2 * i + 2 # 오른쪽 자식
 
    # 왼쪽 자식이 루트보다 크면 largest 갱신
    if left < n and arr[left] > arr[largest]:
        largest = left
 
    # 오른쪽 자식이 현재 largest보다 크면 갱신
    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)
    # 마지막 부모 노드부터 heapify
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
 
 
def heap_sort(arr):
    """힙 정렬 (오름차순)"""
    n = len(arr)
 
    # 1. 힙 생성
    build_heap(arr)
 
    # 2. 하나씩 루트(최대값)를 뒤로 보냄
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]  # 루트와 끝 교환
        heapify(arr, i, 0)  # 줄어든 힙에 대해 heapify
 
 
# 실행 부분
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)
 

ZGVmIGhlYXBpZnkoYXJyLCBuLCBpKToKICAgICIiImFyclswLi5uLTFdIOuylOychOyXkOyEnCBp66W8IOujqO2KuOuhnCDtlZjripQg7ISc67iM7Yq466as66W8IO2emeycvOuhnCDrp4zrk6YiIiIKICAgIGxhcmdlc3QgPSBpICAgICAgICMg66Oo7Yq4CiAgICBsZWZ0ID0gMiAqIGkgKyAxICAjIOyZvOyqvSDsnpDsi50KICAgIHJpZ2h0ID0gMiAqIGkgKyAyICMg7Jik66W47Kq9IOyekOyLnQoKICAgICMg7Jm87Kq9IOyekOyLneydtCDro6jtirjrs7Tri6Qg7YGs66m0IGxhcmdlc3Qg6rCx7IugCiAgICBpZiBsZWZ0IDwgbiBhbmQgYXJyW2xlZnRdID4gYXJyW2xhcmdlc3RdOgogICAgICAgIGxhcmdlc3QgPSBsZWZ0CgogICAgIyDsmKTrpbjsqr0g7J6Q7Iud7J20IO2YhOyerCBsYXJnZXN067O064ukIO2BrOuptCDqsLHsi6AKICAgIGlmIHJpZ2h0IDwgbiBhbmQgYXJyW3JpZ2h0XSA+IGFycltsYXJnZXN0XToKICAgICAgICBsYXJnZXN0ID0gcmlnaHQKCiAgICAjIOujqO2KuOqwgCDqsIDsnqUg7YGwIOqwkuydtCDslYTri4jrqbQg6rWQ7ZmYIO2bhCDsnqzqt4Ag7Zi47LacCiAgICBpZiBsYXJnZXN0ICE9IGk6CiAgICAgICAgYXJyW2ldLCBhcnJbbGFyZ2VzdF0gPSBhcnJbbGFyZ2VzdF0sIGFycltpXQogICAgICAgIGhlYXBpZnkoYXJyLCBuLCBsYXJnZXN0KQoKCmRlZiBidWlsZF9oZWFwKGFycik6CiAgICAiIiLrsLDsl7TsnYQg7LWc64yAIO2emeycvOuhnCDrs4DtmZgiIiIKICAgIG4gPSBsZW4oYXJyKQogICAgIyDrp4jsp4Drp4kg67aA66qoIOuFuOuTnOu2gO2EsCBoZWFwaWZ5CiAgICBmb3IgaSBpbiByYW5nZShuIC8vIDIgLSAxLCAtMSwgLTEpOgogICAgICAgIGhlYXBpZnkoYXJyLCBuLCBpKQoKCmRlZiBoZWFwX3NvcnQoYXJyKToKICAgICIiIu2emSDsoJXroKwgKOyYpOumhOywqOyInCkiIiIKICAgIG4gPSBsZW4oYXJyKQoKICAgICMgMS4g7Z6ZIOyDneyEsQogICAgYnVpbGRfaGVhcChhcnIpCgogICAgIyAyLiDtlZjrgpjslKkg66Oo7Yq4KOy1nOuMgOqwkinrpbwg65Kk66GcIOuztOuDhAogICAgZm9yIGkgaW4gcmFuZ2UobiAtIDEsIDAsIC0xKToKICAgICAgICBhcnJbMF0sIGFycltpXSA9IGFycltpXSwgYXJyWzBdICAjIOujqO2KuOyZgCDrgZ0g6rWQ7ZmYCiAgICAgICAgaGVhcGlmeShhcnIsIGksIDApICAjIOykhOyWtOuToCDtnpnsl5Ag64yA7ZW0IGhlYXBpZnkKCgojIOyLpO2WiSDrtoDrtoQKaWYgX19uYW1lX18gPT0gIl9fbWFpbl9fIjoKICAgIGFyciA9IFs1LCAxMCwgMjY0LCAzNjIsIDg2NSwgNjMsIDk0LCA0NzUsIDEzNSwgOTMyLAogICAgICAgICAgIDI1LCA5LCAzMywgMjg3LCAzMzIsIDc0NSwgMzc3LCA4MjAsIDYyLCAxXQoKICAgICMgMS4g7Z6ZIOyDneyEsSDqsrDqs7wg7Lac66ClCiAgICBoZWFwX2FyciA9IGFycls6XSAgIyDrs7XsgqwKICAgIGJ1aWxkX2hlYXAoaGVhcF9hcnIpCiAgICBwcmludCgiMS4g7IOd7ISx65CcIO2emSDrsLDsl7Q6IiwgaGVhcF9hcnIpCgogICAgIyAyLiDtnpkg7KCV66CsIOqysOqzvCDstpzroKUKICAgIHNvcnRlZF9hcnIgPSBhcnJbOl0gICMg67O17IKsCiAgICBoZWFwX3NvcnQoc29ydGVkX2FycikKICAgIHByaW50KCIyLiDsoJXroKzrkJwg67Cw7Je0OiIsIHNvcnRlZF9hcnIpCg==