Convertir le tas minimum en tas maximum
Étant donné une représentation matricielle de min Heap, convertissez-le en max Heap.
Exemples :
Saisir: arr[] = {3 5 9 6 8 20 10 12 18 9}
3
/
5 9
/ /
6 8 20 10
/ /
12 18 9Sortir: arr[] = {20 18 10 12 9 9 3 5 6 8}
20
/
18 10
/ /
12 9 9 3
/ /
5 6 8Saisir: arr[] = {3 4 8 11 13}
Sortir: arr[] = {13 11 8 4 3}
L'idée est simplement de créer Max Heap sans se soucier de l'entrée. Commencez par le nœud interne le plus bas et le plus à droite de Min-Heap et regroupez tous les nœuds internes de manière ascendante pour construire le tas Max.
Suivez les étapes indiquées pour résoudre le problème :
- Appelez la fonction Heapify depuis le nœud interne le plus à droite de Min-Heap
- Heapifiez tous les nœuds internes de manière ascendante pour créer un tas maximum
- Imprimer le tas maximum
Algorithme: Voici un algorithme pour convertir un tas min en un tas max :
- Commencez par le dernier nœud non-feuille du tas (c'est-à-dire le parent du dernier nœud feuille). Pour un tas binaire, ce nœud est situé au niveau de l'index ((n - 1)/2) où n est le nombre de nœuds dans le tas.
- Pour chaque nœud non-feuille, effectuez un 'empiler' opération pour corriger la propriété du tas. Dans un tas min, cette opération consiste à vérifier si la valeur du nœud est supérieure à celle de ses enfants et si c'est le cas, à échanger le nœud avec le plus petit de ses enfants. Dans un tas max, l'opération consiste à vérifier si la valeur du nœud est inférieure à celle de ses enfants et si c'est le cas, à échanger le nœud avec le plus grand de ses enfants.
- Répétez l’étape 2 pour chacun des nœuds non-feuilles en remontant le tas. Lorsque vous atteignez la racine du tas, le tas entier devrait maintenant être un tas maximum.
Vous trouverez ci-dessous la mise en œuvre de l’approche ci-dessus :
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 ?>
Sortir
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
Complexité temporelle : O(N) pour plus de détails, veuillez vous référer : Temps Complexité de la construction d'un tas
Espace auxiliaire : SUR)
