def heap_sort(a):
    build_heap(a)
    heap_size = len(a) - 1
    for i in range(len(a) - 1, 0, -1):
        a[0], a[i] = a[i], a[0]
        heap_size -= 1
        heapify(a, 0, heap_size)
    return a

def build_heap(a):
    heap_size = len(a) - 1
    for i in range(len(a)//2, -1, -1):
        heapify(a, i, heap_size)

def heapify(a, i, heap_size):
    l = 2 * i
    r = 2 * i + 1
    if l <= heap_size and a[l] > a[i]:
        largest = l
    else:
        largest = i
    if r <= heap_size and a[r] > a[largest]:
        largest = r
    if largest != i:
        a[i], a[largest] = a[largest], a[i]
        heapify(a, largest, heap_size)