import random

def randomList(count:int=10) -> list:
    '''return a random list with elements from 0 to count-1'''
    return random.sample(range(count), count)

# Recursively. Θ(lgn)
def maxHeapify(array, arrayLength, fatherIndex):
    '''Maintain the max-heap property from the fatherIndex-th element'''
    largestIndex = fatherIndex
    leftIndex = 2 * fatherIndex
    rightIndex = leftIndex+1

    # Keep indices lower than len of the array
    if leftIndex<arrayLength and array[leftIndex]>array[largestIndex]:
        largestIndex = leftIndex
    if rightIndex<arrayLength and array[rightIndex]>array[largestIndex]:
        largestIndex = rightIndex
    if largestIndex != fatherIndex:
        array[largestIndex], array[fatherIndex] = array[fatherIndex], array[largestIndex]
        maxHeapify(array, arrayLength, largestIndex)

# Cyclically. Θ(lgn)
def maxHeapify(array, arrayLength, fatherIndex):
    '''Maintain the max-heap property from the fatherIndex-th element'''
    largestIndex = fatherIndex

    while True:
        leftIndex = 2 * fatherIndex
        rightIndex = leftIndex+1

        # Keep indices lower than len of the array
        if leftIndex<arrayLength and array[leftIndex]>array[largestIndex]:
            largestIndex = leftIndex
        if rightIndex<arrayLength and array[rightIndex]>array[largestIndex]:
            largestIndex = rightIndex
        if largestIndex != fatherIndex:
            array[largestIndex], array[fatherIndex] = array[fatherIndex], array[largestIndex]
            fatherIndex = largestIndex
        else:break

# Θ(n)
def buildMaxHeap(array):
    '''Convert an original array into a max heap'''
    for i in reversed(range(len(array)//2)):
        maxHeapify(array, len(array), i)

# Θ(nlgn)
def heapSort(array):
    '''Heap sort a designated array'''
    if len(array)<=1:
        return
    buildMaxHeap(array)
    for i in reversed(range(1, len(array))):
        array[0], array[i] = array[i], array[0]
        maxHeapify(array, i, 0)

# Trial
array = randomList()
print(array)
heapSort(array)
print(array)