def heapify(arr,n,i): #to form max heap
    highest=i
    left=(2*i)+1 #left node of the parent
    right=left+1 #right node of the parent

    #extracting the largest of the three
    #i.e. parent and its children
    if left<n and arr[i]<arr[left]:
        highest=left
    if right<n and arr[highest]<arr[right]:
        highest=right

    #if the chosen parent is not the highest
    #swap it with the largest
    if highest!=i:
        #swapping the largest
        arr[i],arr[highest]=arr[highest],arr[i]
        heapify(arr,n,highest)

def heapSort(arr):
    n=len(arr)
    #n//2 gives the first parent node
    #every node after n//2 is a leaf node.
    for i in range(n//2,-1,-1):
        heapify(arr,n,i)
    
    #heapifying after deletion operation
    for i in range(n-1,0,-1):
        #swapping the last element with the root
        arr[0],arr[i]=arr[i],arr[0] 
        heapify(arr,i,0)

arr = [60,50,45,40,35,20,25,30]
heapSort(arr)
n = len(arr)
print("Sorted array is: ")    
for i in range(n):
    print("%d " % arr[i], end='')# your code goes here