def heap_sort(arr):
    
    heapify(arr)  
    end = len(arr) - 1
    while end > 0:
        arr[end], arr[0] = arr[0], arr[end]
        shift_down(arr, 0, end - 1)
        end -= 1
    return arr
def heapify(arr):
    start = len(arr) // 2
    while start >= 0:
        shift_down(arr, start, len(arr) - 1)
        start -= 1
def shift_down(arr, start, end):
    root = start
    while root * 2 + 1 <= end:
        child = root * 2 + 1
        if child + 1 <= end and arr[child] < arr[child + 1]:
            child += 1
        if child <= end and arr[root] < arr[child]:
            arr[root], arr[child] = arr[child], arr[root]
            root = child
        else:
            return
def heap_sort(VAR_0):
    heapify(VAR_0)
    end = len(VAR_0) - 1
    while end > 0:
        VAR_0[end], VAR_0[0] = VAR_0[0], VAR_0[end]
        shift_down(VAR_0, 0, end - 1)
        end -= 1
    return VAR_0
def heapify(VAR_0):
    start = len(VAR_0) // 2
    while start >= 0:
       
        shift_down(VAR_0, start, len(VAR_0) - 1)
        start -= 1
def shift_down(VAR_0, start, end):
    root = start
    while root * 2 + 1 <= end:
        child = root * 2 + 1
        if child + 1 <= end and VAR_0[child] < VAR_0[child + 1]:
            child += 1
        if child <= end and VAR_0[root] < VAR_0[child]:
            VAR_0[root], VAR_0[child] = VAR_0[child], VAR_0[root]
            root = child
        else:
            return