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
def heapify ( arr , n , i ) : NEW_LINE INDENT smallest = i NEW_LINE l = 2 * i + 1 NEW_LINE r = 2 * i + 2 NEW_LINE if l < n and arr [ l ] < arr [ smallest ] : NEW_LINE INDENT smallest = l NEW_LINE DEDENT if r < n and arr [ r ] < arr [ smallest ] : NEW_LINE INDENT smallest = r NEW_LINE DEDENT if smallest != i : NEW_LINE INDENT ( arr [ i ] , arr [ smallest ] ) = ( arr [ smallest ] , arr [ i ] ) NEW_LINE heapify ( arr , n , smallest ) NEW_LINE DEDENT DEDENT def heapSort ( arr , n ) : NEW_LINE INDENT for i in range ( int ( n / 2 ) - 1 , - 1 , - 1 ) : NEW_LINE INDENT heapify ( arr , n , i ) NEW_LINE DEDENT for i in range ( n - 1 , - 1 , - 1 ) : NEW_LINE INDENT arr [ 0 ] , arr [ i ] = arr [ i ] , arr [ 0 ] NEW_LINE heapify ( arr , i , 0 ) NEW_LINE DEDENT DEDENT def printArray ( arr , n ) : NEW_LINE INDENT for i in range ( n ) : NEW_LINE INDENT print ( arr [ i ] , end = " ▁ " ) NEW_LINE DEDENT print ( ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 4 , 6 , 3 , 2 , 9 ] NEW_LINE n = len ( arr ) NEW_LINE heapSort ( arr , n ) NEW_LINE print ( " Sorted ▁ array ▁ is ▁ " ) NEW_LINE printArray ( arr , n ) NEW_LINE DEDENT