Konvertera min hög till maxhögen
Med tanke på en matrisrepresentation av Min Heap konvertera den till Max Heap.
Exempel:
Input: arr [] = {3 5 9 6 8 20 10 12 18 9}
3
/
5 9
//
6 8 20 10
/ /
12 18 9Produktion: arr [] = {20 18 10 12 9 9 3 5 6 8}
20
/
18 10
//
12 9 9 3
/ /
5 6 8Input: arr [] = {3 4 8 11 13}
Produktion: arr [] = {13 11 8 4 3}
Idén är helt enkelt att bygga maxhög utan att bry sig om ingången. Börja från den nedre och högsta interna noden för min-heap och heapify alla interna noder på bottenvätten för att bygga maxhögen.
Följ de givna stegen för att lösa problemet:
- Ring heapify-funktionen från den högsta interna noden för min-heap
- Heapify alla interna noder på botten upp för att bygga maxhög
- Skriv ut max-heap
Algoritm: Här är en algoritm för att konvertera en minhög till en maxhög :
- Börja vid den sista icke-bladnoden på högen (dvs föräldern till den sista bladnoden). För en binär hög är denna nod belägen på indexgolvet ((n - 1)/2) där n är antalet noder i högen.
- För varje icke-blad nod utför du en 'Heapify' drift för att fixa högegenskapen. I en minhög innebär denna operation att kontrollera om värdet på noden är större än för sina barn och i så fall att byta noden med de mindre av sina barn. I maximal innebär operationen att kontrollera om nodens värde är mindre än för sina barn och i så fall byter noden med de större av sina barn.
- Upprepa steg 2 för var och en av de icke-bladnoder som arbetar dig uppför högen. När du når roten till högen bör hela högen nu vara en maxhög.
Nedan är implementeringen av ovanstående tillvägagångssätt:
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 ?>
Produktion
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
Tidskomplexitet: O (n) För mer information, se: Tidskomplexiteten i att bygga en hög
Hjälputrymme: PÅ)
