Iterative HeapSort | function build Max Heap where value of each child is always smaller than value of their parent ; if child is bigger than parent ; swap child and parent until parent is smaller ; swap value of first indexed with last indexed ; maintaining heap property after each swapping ; if left child is smaller than right child point index variable to right child ; if parent is smaller than child then swapping parent with child having higher value ; Driver Code
def buildMaxHeap ( arr , n ) : NEW_LINE INDENT for i in range ( n ) : NEW_LINE INDENT if arr [ i ] > arr [ int ( ( i - 1 ) / 2 ) ] : NEW_LINE INDENT j = i NEW_LINE while arr [ j ] > arr [ int ( ( j - 1 ) / 2 ) ] : NEW_LINE INDENT ( arr [ j ] , arr [ int ( ( j - 1 ) / 2 ) ] ) = ( arr [ int ( ( j - 1 ) / 2 ) ] , arr [ j ] ) NEW_LINE j = int ( ( j - 1 ) / 2 ) NEW_LINE DEDENT DEDENT DEDENT DEDENT def heapSort ( arr , n ) : NEW_LINE INDENT buildMaxHeap ( arr , n ) NEW_LINE for i in range ( n - 1 , 0 , - 1 ) : NEW_LINE INDENT arr [ 0 ] , arr [ i ] = arr [ i ] , arr [ 0 ] NEW_LINE j , index = 0 , 0 NEW_LINE while True : NEW_LINE INDENT index = 2 * j + 1 NEW_LINE if ( index < ( i - 1 ) and arr [ index ] < arr [ index + 1 ] ) : NEW_LINE INDENT index += 1 NEW_LINE DEDENT if index < i and arr [ j ] < arr [ index ] : NEW_LINE INDENT arr [ j ] , arr [ index ] = arr [ index ] , arr [ j ] NEW_LINE DEDENT j = index NEW_LINE if index >= i : NEW_LINE INDENT break NEW_LINE DEDENT DEDENT DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 10 , 20 , 15 , 17 , 9 , 21 ] NEW_LINE n = len ( arr ) NEW_LINE print ( " Given ▁ array : ▁ " ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT print ( arr [ i ] , end = " ▁ " ) NEW_LINE DEDENT print ( ) NEW_LINE heapSort ( arr , n ) NEW_LINE print ( " Sorted ▁ array : ▁ " ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT print ( arr [ i ] , end = " ▁ " ) NEW_LINE DEDENT DEDENT