human
HeapSort | To heapify subtree rooted at index i . n is size of heap.
Initialize largest as root.
left = 2 * i + 1.
right = 2 * i + 2.
See if left child of root exists and is greater than root.
See if right child of root exists and is greater than root.
Change root , if needed.
Heapify the root ..
The main function to sort an array of given size.
Build a maxheap ..
One by one extract elements.
swap.
call max heapify on the reduced heap.
Driver code"
How can the above be solved in Python?
 Give me a code to heapSort and the other steps required?
assistant
#Here is code to heapSort and the other steps required.
 def heapify ( arr , n , i ) :
	largest = i
	l = 2 * i + 1
	r = 2 * i + 2
	if l < n and arr [ largest ] < arr [ l ] :
		largest = l
	if r < n and arr [ largest ] < arr [ r ] :
		largest = r
	if largest != i :
		arr [ i ] , arr [ largest ] = arr [ largest ] , arr [ i ]
		heapify ( arr , n , largest )
def heapSort ( arr ) :
	n = len ( arr )
	for i in range ( n // 2 - 1 , - 1 , - 1 ) :
		heapify ( arr , n , i )
	for i in range ( n - 1 , 0 , - 1 ) :
		arr [ i ] , arr [ 0 ] = arr [ 0 ] , arr [ i ]
		heapify ( arr , i , 0 )
arr = [ 12 , 11 , 13 , 5 , 6 , 7 ]
heapSort ( arr )
n = len ( arr )
print ( " Sorted ▁ array ▁ is " )
for i in range ( n ) :
	print ( " % d " % arr [ i ] ) ,