Lexicographical ordering using Heap Sort | Used for index in heap ; Predefining the heap array ; Defining formation of the heap ; Iterative heapiFy ; Just swapping if the element is smaller than already stored element ; Swapping the current index with its child ; Moving upward in the heap ; Defining heap sort ; Taking output of the minimum element ; Set first element as a last one ; Decrement of the size of the string ; Initializing the left and right index ; Process of heap sort If root element is minimum than its both of the child then break ; Otherwise checking that the child which one is smaller , swap them with parent element ; Swapping ; Changing the left index and right index ; Utility function ; To heapiFy ; Calling heap sort function ; Driver Code
x = - 1 ; NEW_LINE heap = [ 0 ] * 1000 ; NEW_LINE def heapForm ( k ) : NEW_LINE INDENT global x ; NEW_LINE x += 1 ; NEW_LINE heap [ x ] = k ; NEW_LINE child = x ; NEW_LINE index = x // 2 ; NEW_LINE while ( index >= 0 ) : NEW_LINE INDENT if ( heap [ index ] > heap [ child ] ) : NEW_LINE INDENT tmp = heap [ index ] ; NEW_LINE heap [ index ] = heap [ child ] ; NEW_LINE heap [ child ] = tmp ; NEW_LINE child = index ; NEW_LINE index = index // 2 ; NEW_LINE DEDENT else : NEW_LINE INDENT break ; NEW_LINE DEDENT DEDENT DEDENT def heapSort ( ) : NEW_LINE INDENT global x ; NEW_LINE while ( x >= 0 ) : NEW_LINE INDENT k = heap [ 0 ] ; NEW_LINE print ( k , end = " ▁ " ) ; NEW_LINE heap [ 0 ] = heap [ x ] ; NEW_LINE x = x - 1 ; NEW_LINE tmp = - 1 ; NEW_LINE index = 0 ; NEW_LINE length = x ; NEW_LINE left1 = 1 ; NEW_LINE right1 = left1 + 1 ; NEW_LINE while ( left1 <= length ) : NEW_LINE INDENT if ( heap [ index ] <= heap [ left1 ] and heap [ index ] <= heap [ right1 ] ) : NEW_LINE INDENT break ; NEW_LINE DEDENT else : NEW_LINE INDENT if ( heap [ left1 ] < heap [ right1 ] ) : NEW_LINE INDENT tmp = heap [ index ] ; NEW_LINE heap [ index ] = heap [ left1 ] ; NEW_LINE heap [ left1 ] = tmp ; NEW_LINE index = left1 ; NEW_LINE DEDENT else : NEW_LINE INDENT tmp = heap [ index ] ; NEW_LINE heap [ index ] = heap [ right1 ] ; NEW_LINE heap [ right1 ] = tmp ; NEW_LINE index = right1 ; NEW_LINE DEDENT DEDENT left1 = 2 * left1 ; NEW_LINE right1 = left1 + 1 ; NEW_LINE DEDENT DEDENT DEDENT def sort ( k , n ) : NEW_LINE INDENT for i in range ( n ) : NEW_LINE INDENT heapForm ( k [ i ] ) ; NEW_LINE DEDENT heapSort ( ) ; NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ " banana " , " orange " , " apple " , " pineapple " , " berries " , " lichi " ] ; NEW_LINE n = len ( arr ) ; NEW_LINE sort ( arr , n ) ; NEW_LINE DEDENT