Converteer min heap naar max heap
Gegeven een array -weergave van min heap converteer het naar max heap.
Voorbeelden:
Invoer: arr [] = {3 5 9 6 8 20 10 12 18 9}
3
/
5 9
//
6 8 20 10
/ / /
12 18 9Uitvoer: arr [] = {20 18 10 12 9 9 3 5 6 8}
20
/
18 10
//
12 9 3
/ / /
5 6 8Invoer: arr [] = {3 4 8 11 13}
Uitvoer: arr [] = {13 11 8 4 3}
Het idee is eenvoudig Max Heap bouwen zonder de invoer te geven. Begin van de meest onderste en meest rechtse interne knooppunt van min-heap en verdrijft alle interne knooppunten in de onderste manier om de maximale heap te bouwen.
Volg de gegeven stappen om het probleem op te lossen:
- Roep de heapify-functie aan vanaf het meest rechtse interne knooppunt van min-heap
- Alle interne knooppunten op de onderste manier om Max Heap te bouwen.
- Druk de max-heap af
Algoritme: Hier is een Algoritme voor het converteren van een min hoop naar een maximale heap :
- Begin bij het laatste niet-blad knooppunt van de hoop (d.w.z. de ouder van het laatste bladknooppunt). Voor een binaire hoop bevindt dit knooppunt zich op de indexvloer ((n - 1)/2) waarbij n het aantal knooppunten in de heap is.
- Voer een niet-bladknoop een 'SEAPIFY' bewerking om de eigenschap Heap te repareren. In een min hoop omvat deze operatie het controleren of de waarde van het knooppunt groter is dan die van zijn kinderen en als dit het knooppunt ruilen met de kleinere van zijn kinderen. In een maximale heap omvat de operatie het controleren of de waarde van het knooppunt minder is dan die van zijn kinderen en als dit het knooppunt ruilen met de grootste kinderen.
- Herhaal stap 2 voor elk van de niet-blad knooppunten die je op de hoop werken. Wanneer u de wortel van de hoop bereikt, zou de hele hoop nu een maximale heap moeten zijn.
Hieronder is de implementatie van de bovenstaande aanpak:
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 ?>
Uitvoer
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
Tijdcomplexiteit: O (n) Voor meer informatie kunt u: Zie: Tijdcomplexiteit van het bouwen van een hoop
Hulpruimte: Op)
