Lexicographical ordering using Heap Sort | C ++ implementation to print the string in Lexicographical order ; 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
#include <iostream> NEW_LINE #include <string> NEW_LINE using namespace std ; int x = -1 ; string heap [ 1000 ] ; void heapForm ( string k ) { x ++ ; heap [ x ] = k ; int child = x ; string tmp ; int index = x / 2 ; while ( index >= 0 ) { if ( heap [ index ] > heap [ child ] ) { tmp = heap [ index ] ; heap [ index ] = heap [ child ] ; heap [ child ] = tmp ; child = index ; index = index / 2 ; } else { break ; } } } void heapSort ( ) { int left1 , right1 ; while ( x >= 0 ) { string k ; k = heap [ 0 ] ; cout << k << " ▁ " ; heap [ 0 ] = heap [ x ] ; x = x - 1 ; string tmp ; int index = 0 ; int length = x ; left1 = 1 ; right1 = left1 + 1 ; while ( left1 <= length ) { if ( heap [ index ] <= heap [ left1 ] && heap [ index ] <= heap [ right1 ] ) { break ; } else { if ( heap [ left1 ] < heap [ right1 ] ) { tmp = heap [ index ] ; heap [ index ] = heap [ left1 ] ; heap [ left1 ] = tmp ; index = left1 ; } else { tmp = heap [ index ] ; heap [ index ] = heap [ right1 ] ; heap [ right1 ] = tmp ; index = right1 ; } } left1 = 2 * left1 ; right1 = left1 + 1 ; } } } void sort ( string k [ ] , int n ) { for ( int i = 0 ; i < n ; i ++ ) { heapForm ( k [ i ] ) ; } heapSort ( ) ; } int main ( ) { string arr [ ] = { " banana " , " orange " , " apple " , " pineapple " , " berries " , " lichi " } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; sort ( arr , n ) ; }