Given an integer array, check if it represents min-heap or not.

For example, the first array represents a min-heap, but the second array isn’t as it violate the heap property.

 
min-heap-array-1
min-heap-example-1

min-heap-array-2
min-heap-example-2
 

Practice this problem

 
Since the input is an array, the heap’s structural property (all levels except the last level are full) cannot be violated. We only have to worry about the Min Heap Property (the priority of a node is at least as large as that of its parent) for a given problem.

Since array indexing begins from 0, for a given index i of an array of size n, if 2×i + 2 > n is true then A[i] represents a leaf node. Otherwise, when 2×i + 2 <= n is true, A[i] represents internal heap node.

For instance, consider array [2, 3, 4, 5, 10, 15] of size n = 6. Here, [2, 3, 4] are internal nodes as 2×i + 2 <= 6 is true and [5, 10, 15] are leaf nodes as 2×i + 2 > 6 is true.

 
min-heap-with-nodes-marked

Now that we know how to differentiate between a leaf node and an internal node based on the given array index and the total number of nodes, let’s return to the given problem.

Recursive Solution

We can efficiently solve this problem by using recursion. The idea is to start from the root node (at index 0) and check if the left and right child (if any) of the root node is greater than the root node or not. If true, recursively call the procedure for both its children; otherwise, return false from the function. Following is the complete algorithm:

  • If the current node is a leaf node, return true as every leaf node is a heap.
  • If the current node is an internal node,
    • Recursively check if the left child is min-heap or not.
    • Recursively check if the right child is min-heap or not (if it exists).
    • Return true if both left and right child are min-heap; otherwise, return false.

The algorithm can be implemented as follows in C++, Java, and Python:

C++


Download  Run Code

Output:

The given array is a min-heap

Java


Download  Run Code

Output:

The given array is a min-heap

Python


Download  Run Code

Output:

The given list is a min-heap

Iterative Solution

As recursion is costly, we can easily convert the above recursive function into an iterative one. The implementation can be seen below in C++, Java, and Python:

C++


Download  Run Code

Output:

The given array is a min-heap

Java


Download  Run Code

Output:

The given array is a min-heap

Python


Download  Run Code

Output:

The given list is a min-heap

The time complexity of the above solution is O(n) and doesn’t require any extra space, where n is the size of the input.

 
Exercise: Given an integer array, check if it represents max-heap or not.