human
Heap Sort for decreasing order using min heap | To heapify a subtree rooted with node i which is an index in arr [ ] . n is size of heap.
Initialize smalles as root.
left = 2 * i + 1.
right = 2 * i + 2.
If left child is smaller than root.
If right child is smaller than smallest so far.
If smallest is not root.
Recursively heapify the affected sub - tree.
main function to do heap sort.
Build heap ( rearrange array ).
One by one extract an element from heap.
Move current root to end.
call max heapify on the reduced heap.
A utility function to print array of size n.
Driver Code"
How can the above be solved in Python?
assistant
#Here is code to heap Sort for decreasing order using min heap and the other steps required.
 def heapify ( arr , n , i ) :
	smallest = i
	l = 2 * i + 1
	r = 2 * i + 2
	if l < n and arr [ l ] < arr [ smallest ] :
		smallest = l
	if r < n and arr [ r ] < arr [ smallest ] :
		smallest = r
	if smallest != i :
		( arr [ i ] , arr [ smallest ] ) = ( arr [ smallest ] , arr [ i ] )
		heapify ( arr , n , smallest )
def heapSort ( arr , n ) :
	for i in range ( int ( n / 2 ) - 1 , - 1 , - 1 ) :
		heapify ( arr , n , i )
	for i in range ( n - 1 , - 1 , - 1 ) :
		arr [ 0 ] , arr [ i ] = arr [ i ] , arr [ 0 ]
		heapify ( arr , i , 0 )
def printArray ( arr , n ) :
	for i in range ( n ) :
		print ( arr [ i ] , end = " ▁ " )
	print ( )
if __name__ == ' _ _ main _ _ ' :
	arr = [ 4 , 6 , 3 , 2 , 9 ]
	n = len ( arr )
	heapSort ( arr , n )
	print ( " Sorted ▁ array ▁ is ▁ " )
	printArray ( arr , n )