CC-13 : Convert Min Heap to Max Heap.
Description:
Given an Min Heap as input, convert it into a Max Heap.
Test cases and expected outputs:
| Input Parameters |
Expected outputs |
Min Heap :
[0] = 1
[1] = 2
[2] = 3
[3] = 4
[4] = 5
[5] = 6
[6] = 7
|
Max Heap :
[0] = 7
[1] = 5
[2] = 6
[3] = 4
[4] = 2
[5] = 1
[6] = 3
|
Pseudocode:
Method minToMaxHeap(int[] arr):
| Set n=arr.length.
|
| Iterate on arr from index (n/2)-1 to index 0:
Call updateHeap(arr, idx).
|
UpdateHeap() (also known as Heapify() method):
| This method takes heap array named arr and index idx of heap array as input variable.
|
| It moves the node data at index idx to its correct position in the Max Heap.
|
| If node data at left child index of idx or right child index of idx is greater than node data at index idx:
Node data at index idx and its child index childIdx with greater node data is swapped.
UpdateHeap() is recursively called with the index of the child childIdx .
|
Code:
public void updateHeap(int[] heap, int idx) {
int parentIdx=idx;
int leftChildIdx= 2*idx+1;
int rightChildIdx=2*idx+2;
if ((leftChildIdx < heap.length) && (heap[leftChildIdx] > heap [parentIdx])) {
parentIdx=leftChildIdx;
}
if ((rightChildIdx < heap.length) && (heap[rightChildIdx] > heap [parentIdx])) {
parentIdx=rightChildIdx;
}
if (parentIdx != idx) {
int temp=heap[idx];
heap[idx]=heap[parentIdx];
heap[parentIdx]=temp;
updateHeap(heap, parentIdx);
}
}
public int[] minToMaxHeap(int[] arr) {
int n=arr.length;
for (int idx = (n / 2) - 1; idx >= 0; idx--) {
updateHeap(arr, idx);
}
return arr;
}
Click here to download and run code and test cases !
Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it.
Be sure to try your own test cases to enhance your understanding !
You can also tweak the code to optimize or add enhancements and custom features.
public class HeapMinToMax {
public void updateHeap(int[] heap, int idx) {
int parentIdx=idx;
int leftChildIdx= 2*idx+1;
int rightChildIdx=2*idx+2;
if ((leftChildIdx < heap.length) && (heap[leftChildIdx] > heap [parentIdx])) {
parentIdx=leftChildIdx;
}
if ((rightChildIdx < heap.length) && (heap[rightChildIdx] > heap [parentIdx])) {
parentIdx=rightChildIdx;
}
if (parentIdx != idx) {
int temp=heap[idx];
heap[idx]=heap[parentIdx];
heap[parentIdx]=temp;
updateHeap(heap, parentIdx);
}
}
public int[] minToMaxHeap(int[] arr) {
int n=arr.length;
for (int idx = (n / 2) - 1; idx >= 0; idx--) {
updateHeap(arr, idx);
}
return arr;
}
public static void printArray(int[] intArray, String label) throws Exception {
// Case 1: The input Array is null !!
if (intArray == null) { System.out.println("\n\n Input Array was null !! \n"); return; }
// Case 2: Print input Array by index (first to last)
System.out.println();
System.out.println("**********************************************************************");
System.out.print(label+" : \n");
int arrayIndex=0;
for (arrayIndex=0; arrayIndex < intArray.length; arrayIndex++) {
System.out.print("["+arrayIndex+"] = "+intArray[arrayIndex]+"\n");
}
System.out.println();
System.out.println("**********************************************************************");
System.out.println();
Thread.sleep(2000);
return;
}
public static void main(String[] args) {
int[] retVal;
try {
HeapMinToMax hp=new HeapMinToMax();
int[] nums= {1,2,3,4,5,6,7};
printArray(nums, "Min Heap");
retVal=hp.minToMaxHeap(nums);
printArray(retVal, "Max Heap");
}catch (Exception exception) {
System.out.print("Exception: "+ exception);
exception.printStackTrace();
}
}
}