CC-10 : Check if input array represents a Max Heap.

Description:

Check if input array represents a Max Heap.

Test cases and expected outputs:

Input Parameters	Expected outputs
Heap1 : [0] = 92 [1] = 44 [2] = 67 [3] = 43 [4] = 12 [5] = 21 [6] = 55	Is Max Heap: true
Heap 2 : [0] = 22 [1] = 44 [2] = 67 [3] = 43 [4] = 12 [5] = 21 [6] = 55	Is Max Heap: false

Pseudocode:

This method takes input array of integers names as nums as a parameter.

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

For each index idx, check the integers at position (2*idx)+1, if it is greater than nums[idx], then input array does not represent a Max Heap, so return false.

Else, for each index idx, check the integers at position (2*idx)+2, if it is greater than nums[idx], then input array does not represent a Max Heap, so return false.

If we have not exited with false status in above loop, then the array represents a Max Heap, so return true.

Code:

public boolean isMaxHeap(int maxHeap[]) {
	for (int idx=0; idx< maxHeap.length;idx++) {
		int leftChildIdx=2+idx+1;
		if (leftChildIdx < maxHeap.length-1) {
			if (maxHeap[idx] < maxHeap[leftChildIdx]) {
				return false;
			}
		}
		int rightChildIdx=2+idx+2;
		if (rightChildIdx < maxHeap.length-1) {
			if (maxHeap[idx] < maxHeap[rightChildIdx]) {
				return false;
			}
		}
	}
	return true;
}

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 HeapMaxCheck {
 
public boolean isMaxHeap(int maxHeap[]) {
	for (int idx=0; idx< maxHeap.length;idx++) {
		int leftChildIdx=2+idx+1;
		if (leftChildIdx < maxHeap.length-1) {
			if (maxHeap[idx] < maxHeap[leftChildIdx]) {
				return false;
			}
		}
		int rightChildIdx=2+idx+2;
		if (rightChildIdx < maxHeap.length-1) {
			if (maxHeap[idx] < maxHeap[rightChildIdx]) {
				return false;
			}
		}
	}
	return true;
}

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) {

boolean retVal;
try {
	HeapMaxCheck hp=new HeapMaxCheck();
	int[] heap1= {92,44, 67, 43, 12,21,55};
	printArray(heap1, "Heap1");
	retVal=hp.isMaxHeap(heap1);
	System.out.print("Is Max Heap: "+ retVal);
	
	int[] heap2= {22,44, 67, 43, 12,21,55};
	printArray(heap2, "Heap 2");
	retVal=hp.isMaxHeap(heap2);
	System.out.print("Is Max Heap: "+ retVal);
	
			
}catch (Exception exception) {
		System.out.print("Exception: "+ exception);
		exception.printStackTrace();
	}
		
}
}