Convertire il mucchio di min in un mucchio massimo
Dato una rappresentazione di array di MIN HEAP convertilo in heap massimo.
Esempi:
Ingresso: arr [] = {3 5 9 6 8 20 10 12 18 9}
3
/
5 9
//
6 8 20 10
/ / /
12 18 9Produzione: arr [] = {20 18 10 12 9 9 3 5 6 8}
20
/
18 10
//
12 9 3
/ / /
5 6 8Ingresso: arr [] = {3 4 8 11 13}
Produzione: arr [] = {13 11 8 4 3}
L'idea è semplicemente costruire un heap massimo senza prendersi cura dell'input. Inizia dal nodo interno più basso e più a destra di Min-heap e accumula tutti i nodi interni nel modo in basso per costruire il mucchio massimo.
Seguire i passaggi indicati per risolvere il problema:
- Chiama la funzione heapify dal nodo interno più a destra di Min-heap
- Accumulare tutti i nodi interni in modo bottom-up per costruire un heap massimo
- Stampa il massimo
Algoritmo: Ecco un Algoritmo per convertire un mucchio di min in un mucchio massimo :
- Inizia dall'ultimo nodo non foglie del heap (cioè il genitore dell'ultimo nodo foglia). Per un mucchio binario questo nodo si trova sul pavimento dell'indice ((n - 1)/2) dove n è il numero di nodi nel mucchio.
- Per ogni nodo non focente eseguire un file 'heapify' operazione per correggere la proprietà heap. In un mucchio di min, questa operazione prevede di verificare se il valore del nodo è maggiore di quello dei suoi figli e, se così, scambiare il nodo con il più piccolo dei suoi figli. In un mucchio massimo, l'operazione prevede di verificare se il valore del nodo è inferiore a quello dei suoi figli e, se così, scambiare il nodo con il più grande dei suoi figli.
- Ripeti il passaggio 2 per ciascuno dei nodi non foglie che si avvicinano al mucchio. Quando raggiungi la radice dell'heap, l'intero heap dovrebbe ora essere un mucchio massimo.
Di seguito è riportato l'implementazione dell'approccio sopra:
C++ // A C++ program to convert min Heap to max Heap #include using namespace std ; // to heapify a subtree with root at given index void MaxHeapify ( int arr [] int i int N ) { int l = 2 * i + 1 ; int r = 2 * i + 2 ; int largest = i ; if ( l < N && arr [ l ] > arr [ i ]) largest = l ; if ( r < N && arr [ r ] > arr [ largest ]) largest = r ; if ( largest != i ) { swap ( arr [ i ] arr [ largest ]); MaxHeapify ( arr largest N ); } } // This function basically builds max heap void convertMaxHeap ( int arr [] int N ) { // Start from bottommost and rightmost // internal node and heapify all internal // nodes in bottom up way for ( int i = ( N - 2 ) / 2 ; i >= 0 ; -- i ) MaxHeapify ( arr i N ); } // A utility function to print a given array // of given size void printArray ( int * arr int size ) { for ( int i = 0 ; i < size ; ++ i ) cout < < arr [ i ] < < ' ' ; } // Driver's code int main () { // array representing Min Heap int arr [] = { 3 5 9 6 8 20 10 12 18 9 }; int N = sizeof ( arr ) / sizeof ( arr [ 0 ]); printf ( 'Min Heap array : ' ); printArray ( arr N ); // Function call convertMaxHeap ( arr N ); printf ( ' n Max Heap array : ' ); printArray ( arr N ); return 0 ; }
C // C program to convert min Heap to max Heap #include void swap ( int * a int * b ) { int temp = * a ; * a = * b ; * b = temp ; } // to heapify a subtree with root at given index void MaxHeapify ( int arr [] int i int N ) { int l = 2 * i + 1 ; int r = 2 * i + 2 ; int largest = i ; if ( l < N && arr [ l ] > arr [ i ]) largest = l ; if ( r < N && arr [ r ] > arr [ largest ]) largest = r ; if ( largest != i ) { swap ( & arr [ i ] & arr [ largest ]); MaxHeapify ( arr largest N ); } } // This function basically builds max heap void convertMaxHeap ( int arr [] int N ) { // Start from bottommost and rightmost // internal node and heapify all internal // nodes in bottom up way for ( int i = ( N - 2 ) / 2 ; i >= 0 ; -- i ) MaxHeapify ( arr i N ); } // A utility function to print a given array // of given size void printArray ( int * arr int size ) { for ( int i = 0 ; i < size ; ++ i ) printf ( '%d ' arr [ i ]); } // Driver's code int main () { // array representing Min Heap int arr [] = { 3 5 9 6 8 20 10 12 18 9 }; int N = sizeof ( arr ) / sizeof ( arr [ 0 ]); printf ( 'Min Heap array : ' ); printArray ( arr N ); // Function call convertMaxHeap ( arr N ); printf ( ' n Max Heap array : ' ); printArray ( arr N ); return 0 ; }
Java // Java program to convert min Heap to max Heap class GFG { // To heapify a subtree with root at given index static void MaxHeapify ( int arr [] int i int N ) { int l = 2 * i + 1 ; int r = 2 * i + 2 ; int largest = i ; if ( l < N && arr [ l ] > arr [ i ] ) largest = l ; if ( r < N && arr [ r ] > arr [ largest ] ) largest = r ; if ( largest != i ) { // swap arr[i] and arr[largest] int temp = arr [ i ] ; arr [ i ] = arr [ largest ] ; arr [ largest ] = temp ; MaxHeapify ( arr largest N ); } } // This function basically builds max heap static void convertMaxHeap ( int arr [] int N ) { // Start from bottommost and rightmost // internal node and heapify all internal // nodes in bottom up way for ( int i = ( N - 2 ) / 2 ; i >= 0 ; -- i ) MaxHeapify ( arr i N ); } // A utility function to print a given array // of given size static void printArray ( int arr [] int size ) { for ( int i = 0 ; i < size ; ++ i ) System . out . print ( arr [ i ] + ' ' ); } // driver's code public static void main ( String [] args ) { // array representing Min Heap int arr [] = { 3 5 9 6 8 20 10 12 18 9 }; int N = arr . length ; System . out . print ( 'Min Heap array : ' ); printArray ( arr N ); // Function call convertMaxHeap ( arr N ); System . out . print ( 'nMax Heap array : ' ); printArray ( arr N ); } } // Contributed by Pramod Kumar
Python3 # A Python3 program to convert min Heap # to max Heap # to heapify a subtree with root # at given index def MaxHeapify ( arr i N ): l = 2 * i + 1 r = 2 * i + 2 largest = i if l < N and arr [ l ] > arr [ i ]: largest = l if r < N and arr [ r ] > arr [ largest ]: largest = r if largest != i : arr [ i ] arr [ largest ] = arr [ largest ] arr [ i ] MaxHeapify ( arr largest N ) # This function basically builds max heap def convertMaxHeap ( arr N ): # Start from bottommost and rightmost # internal node and heapify all # internal nodes in bottom up way for i in range ( int (( N - 2 ) / 2 ) - 1 - 1 ): MaxHeapify ( arr i N ) # A utility function to print a # given array of given size def printArray ( arr size ): for i in range ( size ): print ( arr [ i ] end = ' ' ) print () # Driver Code if __name__ == '__main__' : # array representing Min Heap arr = [ 3 5 9 6 8 20 10 12 18 9 ] N = len ( arr ) print ( 'Min Heap array : ' ) printArray ( arr N ) # Function call convertMaxHeap ( arr N ) print ( 'Max Heap array : ' ) printArray ( arr N ) # This code is contributed by PranchalK
C# // C# program to convert // min Heap to max Heap using System ; class GFG { // To heapify a subtree with // root at given index static void MaxHeapify ( int [] arr int i int n ) { int l = 2 * i + 1 ; int r = 2 * i + 2 ; int largest = i ; if ( l < n && arr [ l ] > arr [ i ]) largest = l ; if ( r < n && arr [ r ] > arr [ largest ]) largest = r ; if ( largest != i ) { // swap arr[i] and arr[largest] int temp = arr [ i ]; arr [ i ] = arr [ largest ]; arr [ largest ] = temp ; MaxHeapify ( arr largest n ); } } // This function basically // builds max heap static void convertMaxHeap ( int [] arr int n ) { // Start from bottommost and // rightmost internal node and // heapify all internal nodes // in bottom up way for ( int i = ( n - 2 ) / 2 ; i >= 0 ; -- i ) MaxHeapify ( arr i n ); } // A utility function to print // a given array of given size static void printArray ( int [] arr int size ) { for ( int i = 0 ; i < size ; ++ i ) Console . Write ( arr [ i ] + ' ' ); } // Driver's Code public static void Main () { // array representing Min Heap int [] arr = { 3 5 9 6 8 20 10 12 18 9 }; int n = arr . Length ; Console . Write ( 'Min Heap array : ' ); printArray ( arr n ); // Function call convertMaxHeap ( arr n ); Console . Write ( 'nMax Heap array : ' ); printArray ( arr n ); } } // This code is contributed by nitin mittal.
JavaScript < script > // javascript program to convert min Heap to max Heap // To heapify a subtree with root at given index function MaxHeapify ( arr i n ) { var l = 2 * i + 1 ; var r = 2 * i + 2 ; var largest = i ; if ( l < n && arr [ l ] > arr [ i ]) largest = l ; if ( r < n && arr [ r ] > arr [ largest ]) largest = r ; if ( largest != i ) { // swap arr[i] and arr[largest] var temp = arr [ i ]; arr [ i ] = arr [ largest ]; arr [ largest ] = temp ; MaxHeapify ( arr largest n ); } } // This function basically builds max heap function convertMaxHeap ( arr n ) { // Start from bottommost and rightmost // internal node and heapify all internal // nodes in bottom up way for ( i = ( n - 2 ) / 2 ; i >= 0 ; -- i ) MaxHeapify ( arr i n ); } // A utility function to print a given array // of given size function printArray ( arr size ) { for ( i = 0 ; i < size ; ++ i ) document . write ( arr [ i ] + ' ' ); } // driver program // array representing Min Heap var arr = [ 3 5 9 6 8 20 10 12 18 9 ]; var n = arr . length ; document . write ( 'Min Heap array : ' ); printArray ( arr n ); convertMaxHeap ( arr n ); document . write ( '
Max Heap array : ' ); printArray ( arr n ); // This code is contributed by 29AjayKumar < /script>
PHP // A PHP program to convert min Heap to max Heap // utility swap function function swap ( & $a & $b ) { $tmp = $a ; $a = $b ; $b = $tmp ; } // to heapify a subtree with root at given index function MaxHeapify ( & $arr $i $n ) { $l = 2 * $i + 1 ; $r = 2 * $i + 2 ; $largest = $i ; if ( $l < $n && $arr [ $l ] > $arr [ $i ]) $largest = $l ; if ( $r < $n && $arr [ $r ] > $arr [ $largest ]) $largest = $r ; if ( $largest != $i ) { swap ( $arr [ $i ] $arr [ $largest ]); MaxHeapify ( $arr $largest $n ); } } // This function basically builds max heap function convertMaxHeap ( & $arr $n ) { // Start from bottommost and rightmost // internal node and heapify all internal // nodes in bottom up way for ( $i = ( int )(( $n - 2 ) / 2 ); $i >= 0 ; -- $i ) MaxHeapify ( $arr $i $n ); } // A utility function to print a given array // of given size function printArray ( $arr $size ) { for ( $i = 0 ; $i < $size ; ++ $i ) print ( $arr [ $i ] . ' ' ); } // Driver code // array representing Min Heap $arr = array ( 3 5 9 6 8 20 10 12 18 9 ); $n = count ( $arr ); print ( 'Min Heap array : ' ); printArray ( $arr $n ); convertMaxHeap ( $arr $n ); print ( ' n Max Heap array : ' ); printArray ( $arr $n ); // This code is contributed by mits ?>
Produzione
Min Heap array : 3 5 9 6 8 20 10 12 18 9 Max Heap array : 20 18 10 12 9 9 3 5 6 8
Complessità temporale: O (n) per i dettagli, consultare: Complessità temporale di costruire un mucchio
Spazio ausiliario: SU)
