Reorder an array according to given indexes | Python3 code to reorder an array according to given indices ; left child in 0 based indexing ; right child in 1 based indexing ; Find largest index from root , left and right child ; Swap arr whenever index is swapped ; Build heap ; Swap the largest element of index ( first element ) with the last element ; Swap arr whenever index is swapped ; Driver Code
def heapify ( arr , index , i ) : NEW_LINE INDENT largest = i NEW_LINE left = 2 * i + 1 NEW_LINE right = 2 * i + 2 NEW_LINE global heapSize NEW_LINE if ( left < heapSize and index [ left ] > index [ largest ] ) : NEW_LINE INDENT largest = left NEW_LINE DEDENT if ( right < heapSize and index [ right ] > index [ largest ] ) : NEW_LINE INDENT largest = right NEW_LINE DEDENT if ( largest != i ) : NEW_LINE INDENT arr [ largest ] , arr [ i ] = arr [ i ] , arr [ largest ] NEW_LINE index [ largest ] , index [ i ] = index [ i ] , index [ largest ] NEW_LINE heapify ( arr , index , largest ) NEW_LINE DEDENT DEDENT def heapSort ( arr , index , n ) : NEW_LINE INDENT global heapSize NEW_LINE for i in range ( int ( ( n - 1 ) / 2 ) , - 1 , - 1 ) : NEW_LINE INDENT heapify ( arr , index , i ) NEW_LINE DEDENT for i in range ( n - 1 , 0 , - 1 ) : NEW_LINE INDENT index [ 0 ] , index [ i ] = index [ i ] , index [ 0 ] NEW_LINE arr [ 0 ] , arr [ i ] = arr [ i ] , arr [ 0 ] NEW_LINE heapSize -= 1 NEW_LINE heapify ( arr , index , 0 ) NEW_LINE DEDENT DEDENT arr = [ 50 , 40 , 70 , 60 , 90 ] NEW_LINE index = [ 3 , 0 , 4 , 1 , 2 ] NEW_LINE n = len ( arr ) NEW_LINE global heapSize NEW_LINE heapSize = n NEW_LINE heapSort ( arr , index , n ) NEW_LINE print ( " Reordered ▁ array ▁ is : ▁ " ) NEW_LINE print ( * arr , sep = ' ▁ ' ) NEW_LINE print ( " Modified ▁ Index ▁ array ▁ is : ▁ " ) NEW_LINE print ( * index , sep = ' ▁ ' ) NEW_LINE