Heap Sort

def heapify(arr, n, i):
    """
    adjust the subtree to a max heap whose root node is i
    :param arr: the (heap) array to be sorted
    :param n: the heap size
    :param i: root node index
    """
    largest = i
    left = 2 * i + 1  # left child index
    right = 2 * i + 2  # right child index

    # if left child exists and bigger than current root, then update the left child as the largest
    if left < n and arr[left] > arr[largest]:
        largest = left

    # if right child exists and bigger than current root, then update the right child as the largest
    if right < n and arr[right] > arr[largest]:
        largest = right

    # if largest has changed(has child larger than the root), then swap the child and recursively process the new subtree
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)


def heap_sort(arr):
    n = len(arr)

    # build a max heap
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    for i in range(n - 1, 0, -1):
        # swap the first element and last element, the now the last element is positioned correctly
        # heap size decreases one(exclude the last one, which is already the largest)
        # heapify the rest of elements, until only one(smallest) element left
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)


# Example
data = [12, 11, 13, 5, 6, 7]
print("Original:", data)

heap_sort(data)
print("After:", data)
# Original: [12, 11, 13, 5, 6, 7]
# After: [5, 6, 7, 11, 12, 13]