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

1. If currentIndex >= nums.length, return true (recursive base condition)
2. Find the index of both the children of the current element and store them in variables named leftChildIndex and rightChildIndex respectively
3. If leftChildIndex is valid and leftChild has value less than the current element, return false
4. If rightChildIndex is valid and rightChild has value less than the current element, return false
5. 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