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
def heapify ( arr , n , i ) : NEW_LINE INDENT largest = i NEW_LINE l = 2 * i + 1 NEW_LINE r = 2 * i + 2 NEW_LINE if l < n and arr [ largest ] < arr [ l ] : NEW_LINE INDENT largest = l NEW_LINE DEDENT if r < n and arr [ largest ] < arr [ r ] : NEW_LINE INDENT largest = r NEW_LINE DEDENT if largest != i : NEW_LINE INDENT arr [ i ] , arr [ largest ] = arr [ largest ] , arr [ i ] NEW_LINE heapify ( arr , n , largest ) NEW_LINE DEDENT DEDENT def heapSort ( arr ) : NEW_LINE INDENT n = len ( arr ) NEW_LINE for i in range ( n // 2 - 1 , - 1 , - 1 ) : NEW_LINE INDENT heapify ( arr , n , i ) NEW_LINE DEDENT for i in range ( n - 1 , 0 , - 1 ) : NEW_LINE INDENT arr [ i ] , arr [ 0 ] = arr [ 0 ] , arr [ i ] NEW_LINE heapify ( arr , i , 0 ) NEW_LINE DEDENT DEDENT arr = [ 12 , 11 , 13 , 5 , 6 , 7 ] NEW_LINE heapSort ( arr ) NEW_LINE n = len ( arr ) NEW_LINE print ( " Sorted ▁ array ▁ is " ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT print ( " % d " % arr [ i ] ) , NEW_LINE DEDENT