CC-11 : Merge 2 Max Heaps.

Description:

Given 2 arrays representing 2 Max Heaps as input, merge the same into a single Max Heap.

Test cases and expected outputs:

Input Parameters	Expected outputs
Heap1 : 93,54,32 Heap2 : 80,72,65	Merged Heap : 93,80,72,65,54,32

Pseudocode:

This method takes 2 input array of integers named as heap1 and heap2 as parameters.

Initialize a PriorityQueue instance named maxHeap to be used as Max Heap. Provide Collections.reverseOrder() as argument to constructor of PriorityQueue, so that it acts as a Max Heap.

Iterate though heap1 from index 0 to index heap1.length-1:

Add heap1[idx]to PriorityQueue.

Iterate though heap2 from index 0 to index heap2.length-1:

Add heap2[idx]to maxHeap.

Instantiate an int array named mergedHeap with size (heap1.length + heap2.length).

Iterate though mergedHeap from index 0 to index mergedHeap.length-1:

Extract top node from maxheap and assign it to mergedHeap[idx].

Return mergedHeap array.

Code:

public int[] merge2Heaps(int[] heap1, int[] heap2) {
	
	PriorityQueue<Integer> maxHeap=new PriorityQueue<Integer>(Collections.reverseOrder());
	for (int iIdx=0; iIdx < heap1.length; iIdx++) {
		maxHeap.add(heap1[iIdx]);		
	}
	for (int iIdx=0; iIdx < heap2.length; iIdx++) {
		maxHeap.add(heap2[iIdx]);		
	}
	int[] mergedHeap=new int[heap1.length+heap2.length];
	for (int iIdx=0; iIdx < mergedHeap.length; iIdx++) {
		mergedHeap[iIdx]=maxHeap.remove();		
	}
	return mergedHeap;
}

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.

import java.util.Collections;
import java.util.PriorityQueue;

public class HeapMerge2Heaps {
 
public int[] merge2Heaps(int[] heap1, int[] heap2) {
	
	PriorityQueue<Integer> maxHeap=new PriorityQueue<Integer>(Collections.reverseOrder());
	for (int iIdx=0; iIdx < heap1.length; iIdx++) {
		maxHeap.add(heap1[iIdx]);		
	}
	for (int iIdx=0; iIdx < heap2.length; iIdx++) {
		maxHeap.add(heap2[iIdx]);		
	}
	int[] mergedHeap=new int[heap1.length+heap2.length];
	for (int iIdx=0; iIdx < mergedHeap.length; iIdx++) {
		mergedHeap[iIdx]=maxHeap.remove();		
	}
	return mergedHeap;
}

public static void printArraySummary(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+" : ");
	int arrayIndex=0;
	for (arrayIndex=0; arrayIndex < intArray.length; arrayIndex++) {
			System.out.print(intArray[arrayIndex]);
			if (arrayIndex < intArray.length-1) {System.out.print(",");}
	} 
	System.out.println();
	System.out.println(" ************************************************************************");
		System.out.println();
		Thread.sleep(2000);
		return;
}

public static void main(String[] args) {

	int[] retVal;
	try {
	HeapMerge2Heaps hp=new HeapMerge2Heaps();
	int[] heap1= {93,54,32};
	int[] heap2 = {80,72,65};
	printArraySummary(heap1, "Heap1");
	printArraySummary(heap2, "Heap2");
	retVal=hp.merge2Heaps(heap1, heap2);
	printArraySummary(retVal, "Merged Heap");	
		
	}catch (Exception exception) {
		System.out.print("Exception: "+ exception);
		exception.printStackTrace();
	}
		
}
}