Convertir el montón min a un montón máximo
Dada una representación de matriz de Min Heap, conviértalo en un montón máximo.
Ejemplos:
Aporte: arr [] = {3 5 9 6 8 20 10 12 18 9}
3
/
5 9
/ /
6 8 20 10
/ /
12 18 9Producción: arr [] = {20 18 10 12 9 9 3 5 6 8}
20
/
18 10
/ /
12 9 9 3
/ /
5 6 8Aporte: arr [] = {3 4 8 11 13}
Producción: arr [] = {13 11 8 4 3}
La idea es simplemente construir un montón máximo sin preocuparse por la entrada. Comience desde el nodo interno más inferior y más derecho de Min-WeAP y acumule todos los nodos internos de la manera ascendente para construir el montón máximo.
Siga los pasos dados para resolver el problema:
- Llame a la función de Heapify desde el nodo interno más a la derecha de Min-HeAP
- Atepifique todos los nodos internos de la manera de abajo hacia arriba para construir un montón máximo
- Imprima el máximo-montón
Algoritmo: Aquí hay un Algoritmo para convertir un montón mínimo en un montón máximo :
- Comience en el último nodo no hojado del montón (es decir, el padre del último nodo de hoja). Para un montón binario, este nodo se encuentra en el piso de índice ((n - 1)/2) donde n es el número de nodos en el montón.
- Para cada nodo no hojado, realice un 'Heapify' operación para arreglar la propiedad Heap. En un montón mínimo, esta operación implica verificar si el valor del nodo es mayor que el de sus hijos y, de ser así, intercambiar el nodo con el más pequeño de sus hijos. En un montón máximo, la operación implica verificar si el valor del nodo es menor que el de sus hijos y, de ser así, intercambiar el nodo con el mayor de sus hijos.
- Repita el paso 2 para cada uno de los nodos que no son de hoja en el montón. Cuando llega a la raíz del montón, todo el montón ahora debe ser un montón máximo.
A continuación se muestra la implementación del enfoque anterior:
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 ?>
Producción
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
Complejidad del tiempo: O (n) Para más detalles, consulte: Complejidad del tiempo de construir un montón
Espacio auxiliar: En)
