# Arrays: Check if array is a min heap

In this article, we will be going to write a program to check if a given array is a min-heap or not

##### Min Heap Properties

A min-heap is a complete binary tree in which the value of a node is smaller than or equal to the values in its child nodes.

The root node a min-heap will hold the smallest value in the entire heap.

In an array representation of min-heap if the current node is at index 'x' then:

Left child index: 2 * x + 1

Right child index: 2 * x + 2

So to check if an array is a min-heap, we have to check if all the nodes follow the above given property and

that the parent is smaller than both of its children

##### Algorithm

- If currentIndex >= nums.length, return true (recursive base condition)
- Find the index of both the children of the current element and store them in variables named leftChildIndex and rightChildIndex respectively
- If leftChildIndex is valid and leftChild has value less than the current element, return false
- If rightChildIndex is valid and rightChild has value less than the current element, return false
- return recursive call isArrayMinHeap(leftChildIndex, nums) && isArrayMinHeap(rightChildIndex, nums)

##### Complexity

Time Complexity : O(n) , where n is the number of elements in the array

Space Complexity: O(LogN)

The Time Complexity will be O(N) as we have to visit and check each node.

The space complexity will be equal to O(Height of the Heap) which is O(LogN) because

of the stack memory consumed by the recursive calls

##### Java Code

```
class HeapOperations {
public static boolean isArrayMinHeap(int currentIndex, int[] nums) {
// base case that the current is out of bounds
if (currentIndex >= nums.length) {
return true;
}
// Find both the child index of the current node
int leftChildIndex = 2 * currentIndex + 1;
int rightChildIndex = 2 * currentIndex + 2;
// Check if both the childs if they are valid or not
if (leftChildIndex < nums.length && nums[leftChildIndex] < nums[currentIndex]) {
// Return false as in minHeap the child is always greater than the parent
return false;
}
if (rightChildIndex < nums.length && nums[rightChildIndex] < nums[currentIndex]) {
// Return false as in minHeap the child is always greater than the parent
return false;
}
// Check both the child nodes recursively
return (isArrayMinHeap(leftChildIndex, nums) && isArrayMinHeap(rightChildIndex,
nums));
}
public static void main(String[] args) {
int[] nums1 = { 1, 3, 2, 4, 6, 5 };
if (isArrayMinHeap(0, nums1)) {
System.out.println("{1, 3, 2, 4, 6, 5} is a Min Heap");
} else {
System.out.println("{1, 3, 2, 4, 6, 5} is not a Min Heap");
}
int[] nums2 = { 8, 2, 6, 12, 11, 10 };
if (isArrayMinHeap(0, nums2)) {
System.out.println("{8, 2, 6, 12, 11, 10} is a Min Heap");
} else {
System.out.println("{8, 2, 6, 12, 11, 10} is not a Min Heap");
}
}
}
```

##### Output

{1, 3, 2, 4, 6, 5} is a Min Heap

{8, 2, 6, 12, 11, 10} is not a Min Heap