def heap_sort(arr,heap_size):
        build_max_heap(arr,heap_size)
        print("Max Heap=",arr)
        for i in range(len(arr[:])-1,0,-1):
            print("i="+str(i))
            arr[1],arr[i]=arr[i],arr[1]
            heap_size=heap_size-1
            max_heapify(arr,1,heap_size)


    def build_max_heap(arr,heap_size):
        for i in range(heap_size//2-1,0,-1):
                max_heapify(arr,i,heap_size)


    def max_heapify(arr,i,heap_size):
            heap_size=len(arr)
            left=2*i+1
            right=2*i+2
            if left<heap_size and arr[left]>arr[i]:
                largest=left
            else:
                largest=i

            if right<heap_size and arr[right]>arr[largest]:
                largest=right

            if i!=largest:
                arr[i],arr[largest]=arr[largest],arr[i]
                max_heapify(arr,largest,heap_size)


    arr=[37, 6, 68, 47, 23, 13, 85, 35, 69, 56]
    print(arr)
    heap_sort(arr,len(arr))
    print ("Sorted array is ",arr)