Given an array representing a Max Heap, in-place convert the array into the min heap in linear time.
The idea is very simple and efficient and inspired from Heap Sort algorithm. The idea is to in-place build the min heap using the array representing max heap. In other words, this is a trick question!! We should not be bothered about whether the given array is max heap or not. The problem is same as building a min-heap from an unsorted array.
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 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 |
#include <iostream> using namespace std; // Data structure for Min Heap class MinHeap { // return left child of A[i] int LEFT(int i) { return (2 * i + 1); } // return right child of A[i] int RIGHT(int i) { return (2 * i + 2); } // Recursive Heapify-down algorithm // the node at index i and its two direct children // violates the heap property 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], A[smallest]); Heapify(A, smallest, size); } } public: // Constructor (Build-Heap - convert max heap to min heap) MinHeap(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); } } // function to remove element with highest priority (present at root) int pop(int A[], int size) { // if heap has no elements if (size <= 0) { return -1; } int top = A[0]; // replace the root of the heap with the last element // of the array A[0] = A[size-1]; // call heapify-down on root node Heapify(A, 0, size - 1); return top; } }; // Convert Max Heap to Min Heap in linear time int main() { /* 9 4 7 1 -2 6 5 */ // array representing max heap int A[] = { 9, 4, 7, 1, -2, 6, 5 }; int n = sizeof(A) / sizeof(A[0]); // build a min heap by initializing it by given array MinHeap pq(A, n); // print the Min Heap /* -2 1 5 9 4 6 7 */ for (int i = 0; i < n; i++) { cout << A[i] << " "; } // pop repeatedly from the heap till it becomes empty /* while (n > 0) { cout << pq.pop(A, n) << " "; n--; }*/ return 0; } |
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 |
import java.util.Arrays; // Data structure for Min Heap class MinHeap { // 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); } // 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); } } // 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; } // Function to convert max heap to min heap public static void convert(int[] A) { // Build-Heap: 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 is same as building of heap i.e. O(n) and the auxiliary space used by the program is O(1).
Exercise: Convert Min Heap to Max Heap in O(n) 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
Classic!
timecomplexity… isnt it nlogn ?
Can you please explain how its o(n)
Thanks for sharing your concerns. This is because building a heap takes O(n) time. Refer this.