In [3]:

    

import math

'''
Functions used to find location within a heap
For heap sort we use max-heaps
A max heap maintains the propety A[parent(i)] >= A[i]
Or, the value of a node is at most the value of its parent
'''

def parent(i):
    return math.floor((i+1)/2)-1

def left(i):
    return 2*(i+1)-1

def right(i):
    return 2*(i+1)

def swap(a, i, j):
    temp = a[i]
    a[i] = a[j]
    a[j] = temp


    

In [9]:

    

def maxHeapify(a, i, heapSize):
    l = left(i)
    r = right(i)
    if l <= heapSize and a[l] > a[i]:
        largest = l
    else:
        largest = i
    if r < heapSize and a[r] > a[largest]:
        largest = r
    if largest != i:
        swap(a, i, largest)
        maxHeapify(a, largest, heapSize)


    

In [12]:

    

a = [16, 4, 10, 14, 7, 9, 3, 2, 8, 1]
print(a)
maxHeapify(a, 1, 10)
print(a)


    

    




[16, 4, 10, 14, 7, 9, 3, 2, 8, 1]
[16, 14, 10, 8, 7, 9, 3, 2, 4, 1]

In [19]:

    

import math

def buildMaxHeap(a):
    for i in range(math.floor(len(a)/2), -1, -1):
        maxHeapify(a, i, len(a))
    return a


    

In [20]:

    

print(buildMaxHeap([4, 1, 3, 2, 16, 9, 10, 14, 8, 7]))


    

    




[16, 14, 10, 8, 7, 9, 3, 2, 4, 1]

In [ ]: