Reorder an array according to given indexes | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int heapSize ; void swap ( int & a , int & b ) { int temp = a ; a = b ; b = temp ; } void heapify ( int arr [ ] , int index [ ] , int i ) { int largest = i ; int left = 2 * i + 1 ; int right = 2 * i + 2 ; if ( left < heapSize && index [ left ] > index [ largest ] ) { largest = left ; } if ( right < heapSize && index [ right ] > index [ largest ] ) { largest = right ; } if ( largest != i ) { swap ( arr [ largest ] , arr [ i ] ) ; swap ( index [ largest ] , index [ i ] ) ; heapify ( arr , index , largest ) ; } } void heapSort ( int arr [ ] , int index [ ] , int n ) { for ( int i = ( n - 1 ) / 2 ; i >= 0 ; i -- ) { heapify ( arr , index , i ) ; } for ( int i = n - 1 ; i > 0 ; i -- ) { swap ( index [ 0 ] , index [ i ] ) ; swap ( arr [ 0 ] , arr [ i ] ) ; heapSize -- ; heapify ( arr , index , 0 ) ; } } int main ( ) { int arr [ ] = { 50 , 40 , 70 , 60 , 90 } ; int index [ ] = { 3 , 0 , 4 , 1 , 2 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; heapSize = n ; heapSort ( arr , index , n ) ; cout << " Reordered ▁ array ▁ is : ▁ STRNEWLINE " ; for ( int i = 0 ; i < n ; i ++ ) cout << arr [ i ] << " ▁ " ; cout << " Modified Index array is : " for ( int i = 0 ; i < n ; i ++ ) cout << index [ i ] << " ▁ " ; return 0 ; }