Given an array representing a Min Heap, convert Min Heap into a Max Heap. The conversion should be done inplace and in linear time.
The idea is very simple and efficient and inspired from Heap Sort algorithm. The problem looks complex at first glance but this problem is no different with building a max-heap from an unsorted array. This is a trick problem! It does not matter whether the given array is a min heap or not. We can simply build the max heap from the given array by starting from the last internal mode (rightmost, bottom-most node) of min Heap and heapify all internal modes in bottom-up manner to build the Max heap.
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 |
#include <iostream> using namespace std; // Data structure for Max Heap class MaxHeap { int LEFT(int i); int RIGHT(int i); void Heapify(int A[], int i, int n); public: MaxHeap(int A[], int n); int pop(int A[], int n); }; // return left child of A[i] int MaxHeap::LEFT(int i) { return (2 * i + 1); } // return right child of A[i] int MaxHeap::RIGHT(int i) { return (2 * i + 2); } // Function to perform Heapify operation void MaxHeap::Heapify(int A[], int i, int n) { // get left and right child of node at index i int left = LEFT(i); int right = RIGHT(i); // compare A[i] with its left & right child and store largest value int largest = i; if (left < n && A[left] > A[i]) largest = left; if (right < n && A[right] > A[largest]) largest = right; // swap with child having greater value & call Heapify on child if (largest != i) { swap(A[i], A[largest]); Heapify(A, largest, n); } } // Class Constructor // (performs Build-Heap operation to convert Min Heap to Max heap) MaxHeap::MaxHeap(int A[], int n) { // call heapify starting from last internal node all the // way upto the root node int i = (n - 2) / 2; while (i >= 0) Heapify(A, i--, n); } // main function int main() { /* Input: Min Heap 1 3 4 6 10 8 5 */ // input array (representing the min heap as shown above) int A[] = { 1, 3, 4, 6, 10, 8, 5 }; int n = sizeof(A) / sizeof(A[0]); // Convert Min Heap to Max heap MaxHeap pq(A, n); /* output: Max Heap 10 6 8 1 3 4 5 */ cout << "Array representation of Max Heap is : "; for (int i = 0; i < n; ++i) cout << A[i] << " "; cout << endl; return 0; } |
Output:
Array representation of Max Heap is : 10 6 8 1 3 4 5
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 |
import java.util.Arrays; // Data structure for Min Heap class ConvertHeap { // return left child of A[i] private static int LEFT(int i) { return (2 * i + 1); } // return right child of A[i] private static int RIGHT(int i) { return (2 * i + 2); } // Utility function to swap two indices in the array private static void swap(int[] A, int i, int j) { int temp = A[i]; A[i] = A[j]; A[j] = temp; } // Recursive Heapify-down algorithm. The node at index i and // its two direct children violates the heap property private static void Heapify(int[] A, int i, int size) { // get left and right child of node at index i int left = LEFT(i); int right = RIGHT(i); int smallest = i; // compare A[i] with its left and right child // and find smallest value if (left < size && A[left] < A[i]) { smallest = left; } if (right < size && A[right] < A[smallest]) { smallest = right; } // swap with child having lesser value and // call heapify-down on the child if (smallest != i) { swap(A, i, smallest); Heapify(A, smallest, size); } } // Constructor (Build-Heap) public static void Convert(int[] A) { // call heapify starting from last internal node all the // way upto the root node int i = (A.length - 2) / 2; while (i >= 0) { Heapify(A, i--, A.length); } } public static void main(String[] args) { /* 9 4 7 1 -2 6 5 */ // array representing max heap int[] A = { 9, 4, 7, 1, -2, 6, 5 }; // build a min heap by initializing it by given array Convert(A); // print the Min Heap /* -2 1 5 9 4 6 7 */ System.out.println(Arrays.toString(A)); } } |
Output:
[-2, 1, 5, 9, 4, 6, 7]
The time complexity of above solution looks like O(nlog(n)) at first look. But the complexity is same as the time complexity of building a heap i.e. O(n).
Exercise: Convert Max Heap to Min Heap in linear time
(1 votes, average: 5.00 out of 5)
Loading...
Thanks for reading.
Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
Leave a Reply
Real tricky indeed!!