Heap.py

def maxHeapify(A,i):
    # it takes the node with index i and puts it in the right position
    # in the heap to make it a maxHeap
    l = Left(i)
    r = Right(i)
    # since we already know that element in index i will be: smaller
    # than the right/left child or higher than both
    # we are storing the index of the higher child in 'largest'
    # which will be the substitution that we need to make, in case that we need to do any substitution
    if l < (len(A)) and A[l] > A[i]:
        largest = l
    else:
        largest = i
    if r < (len(A)) and A[r] > A[largest]:
        largest = r
    # now we already have 'largest' in the index that we want to do the substitution
    # we change values if 'largest' is not our current value 'i'
    # ultimately we recursivelly call maxHeapify in 'largest' to make sure
    # that our element will buble down to the right place it should be
    if largest != i:
        h = A[i]
        A[i] = A[largest]
        A[largest]= h
        maxHeapify(A, largest)

def Right(i):
    # right child index
    return 2*i + 2

def Left(i):
    # left child index
    return 2*i +1

def Parent(i):
    # parent index
    return (i-1)/2

def buildMaxHeap(A):
    # calling maxHeapify for every node except the leaves
    for a in range(int(len(A)//2),-1,-1):
        maxHeapify(A,a)

a = [4,1, 3,2, 16, 9, 10, 14, 8, 7]
print(buildMaxHeap(a))
print(a, '<--')
b= [92, 85, 85, 76, 49, 30, 49, 39, 16, 15, 21, 7, 29, 31, 28]
print(buildMaxHeap(b))
print(b, '<--')
c =  [39, 85, 85, 16, 49, 7, 49, 92, 76, 15, 21, 30, 29, 31, 28]
print(buildMaxHeap(c))
print(c, '<--')