To check if an array represents max-heap / min-heap or not

A heap is a data structure that uses a binary tree for its implementation. It is generally implemented using an array where each element represents a tree node whose parent/children relationship is defined implicitly by their index. After an element is inserted into or deleted from a heap, the heap property may be violated and the heap must be balanced by swapping elements within the array. When we add elements to a heap, we fill this tree-like structure from left to right, level by level. This makes heaps really easy to implement in an array. The root of the tree is the first element of the array.

There are two types of heaps:

1. Max Heap

2. Min Heap

Max Heap:  In this type of heap, the value of the parent node will always be greater than or equal to the value of the child node across the tree, and the node with the highest value will be the root node of the tree.
Max heap uses the descending priority.

Min Heap: In this type of heap, the value of the parent node will always be smaller than or equal to the value of the child node across the tree and the node with the lowest value will be the root node of the tree.
Min heap uses ascending priority. 
Example :

In an array, the first element will contain the root. The next two elements of the array contain its children. The next four contain the four children of the two child nodes, etc. So the elements are filled level by level.

Hence the relationship between them is formed by some formulas, let us discuss that now : 

Note: You can check if a tree does not have any nodes at a certain position then also the formula will work.
Consider this scenario where C has no nodes below it. 

       A
     /    \
    B    C
   /   \
 D    E
Array : [A,B,C,D,E, -, -]
Index :  1  2 3 4  5 6 7
Let's check for node C, it is at index 3. So, its left child should be at 2*i = 2*3 = 6th position which is '-' that means empty node, and similarly for the right child it should be at position 2*i +1 = 7, which is also '-' i.e., empty.
So, it means that there is no node below it. Hence, these formulas will work for all conditions.

Max-heap or Not

Now, for the given problem all we have to do is to check if the array represents a max heap or not. And to verify if a given array is a max-heap, we need to check whether each node satisfies the max-heap property. That is, that key[Parent(i)]≥key[i] for all nodes i except for the root. 
Approach : 
We will traverse all internal nodes and check if the node/element is greater than its children or not. 
1. Start from the root and go till the last interval node/element.
    1.a. If the left child is greater -> return false.
    1.b  If right child is greater -> return false.
2. If both the above conditions are not false, then return true ( Array is correctly represented as max-heap)

Code

Note that, we are using 0^th based indexing, so we will check the left child by 2*i+1 and right child by 2*i + 2. And if i is the index of the child, so the parent of this element is located at floor value of [(i-1)/2].

<strong>//C/C++ code
#include &lt;stdio.h&gt;
int isMaxHeap(int arr[],  int n)
{
    
    for (int i=0; i&lt;=(n-2)/2; i++)//root to last interval node
    {
        if (arr[2*i +1] &gt; arr[i]) // If left child is greater than its parent then return false
                return -1;
        if (2*i+2 &lt; n &amp;&amp; arr[2*i+2] &gt; arr[i])  // If right child is greater its parent then return false
               return -1;
    }
    return 1;
}
 
int main()
{
    int arr[]= {20,15,8,10,5,7,6,2,9,1};
    int n = 10;
 
    int ans = isMaxHeap(arr, n);
    if(ans == -1)
       printf("No");
    else
     printf("Yes");
 
    return 0;
}</strong>

Min-heap or not

As we compared the values in max-heap similarly we will check in min-heap. So, in this problem all we have to do is to check if the array represents a min-heap or not. And to verify if a given array is a min-heap, we need to check whether each node satisfies the min-heap property. That is, that key[Parent(i)]<=key[i] for all nodes i except for the root. That is we will do the exact opposite of what we did for checking if the array is max-heap or not.

Approach :
 We will traverse all internal nodes/elements and check id node is smaller than its children or not.
 1. Start from the root and go till the last interval node/element.
     1.a. If left child is smaller -> return false.
     1.b If right child is smaller -> return false.
2. If both the above conditions are not false, then return true ( Array is correctly represented as min-heap)  

Code : 

<strong>//C/C++ code
#include &lt;stdio.h&gt;
int isMinHeap(int arr[],  int n)
{
    
    for (int i=0; i&lt;=(n-2)/2; i++)//root to last interval node
    {
        if (arr[2*i +1] &lt; arr[i]) // If left child is smaller, return false
                return -1;
        if (2*i+2 &lt; n &amp;&amp; arr[2*i+2] &lt; arr[i])  // If right child is smaller, return false
               return -1;
    }
    return 1;
}
 
int main()
{
    int arr[]= {10,15,30,40,50,100,40};
    int n = 7;
 
    int ans = isMinHeap(arr, n);
    if(ans == -1)
       printf("No");
    else
     printf("Yes");
 
    return 0;
}    
</strong>

Complexity Analysis

The time complexity of the above approach is O(n) and the auxiliary space used is O(1) for both the above programs.​