Given array representation of min Heap, convert it to max Heap in O(n) time.
Example :
Input: arr[] = [3 5 9 6 8 20 10 12 18 9] 3 / 5 9 / / 6 8 20 10 / / 12 18 9 Output: arr[] = [20 18 10 12 9 9 3 5 6 8] OR [any Max Heap formed from input elements] 20 / 18 10 / / 12 9 9 3 / / 5 6 8
The problem might look complex at first look. But our final goal is to only build the max heap. The idea is very simple – we simply build Max Heap without caring about the input. We start from bottom-most and rightmost internal mode of min Heap and heapify all internal modes in bottom up way to build the Max heap.
Below is its implementation
C++
// A C++ program to convert min Heap to max Heap #include<bits/stdc++.h> 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 mode and heapify all internal // modes 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 program to test above functions 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); convertMaxHeap(arr, n); printf ( "
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 mode and heapify all internal // modes 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 program 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); convertMaxHeap(arr, n); System.out.print( "
Max 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 mode and heapify all # internal modes 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) 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 mode and // heapify all internal modes // 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 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); convertMaxHeap(arr, n); Console.Write( "
Max Heap array : " ); printArray(arr, n); } } // This code is contributed by nitin mittal. |
Output :
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
The complexity of above solution might looks like O(nLogn) but it is O(n). Refer this G-Fact for more details.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above
leave a comment
0 Comments