heapsort.py

"""I use arrays to implement the heap and array content start at index 1"""

def max_heapify(array, i):
    left = 2 * i
    right = 2 * i + 1
    N = len(array) - 1
    if left <= N and array[left] > array[i]:
        largest = left
    else:
        largest = i
    if right <= N and array[right] > array[largest]:
        largest = right
    if largest != i:
        temp = array[i]
        array[i] = array[largest]
        array[largest] = temp
        max_heapify(array, largest)
    return array


def build_maxheap(array):
    N = len(array) - 1
    for i in range(N // 2, 0, -1):
        max_heapify(array, i)

        
def heapsort(arr):
    N = len(arr) - 1
    build_maxheap(arr)
    for i in range(N, 1, -1):
        # swap the root with the last leaf node
        arr[1], arr[i] = arr[i], arr[1]
        sub_array = arr[:i]
        max_heapify(sub_array, 1)
        arr = sub_array + arr[i:]
    return arr