How to check if a given array represents a Binary Heap?

Last Updated on December 14, 2022 by Prepbytes

Problem Statement:

Given an array of integers, how We have to check if the given array represents a binary max-heap or not.

First, we’ll see what is Binary heaps and its types

What is Binary Heap?

A Binary Heap is a complete binary tree that follows a heap ordering property. The representation is done as:

• Parent Node: (i-1)/2
• Left Child: (2*i) + 1
• Right Child: (2*i) + 2

The above table shows the indexes of the i^th node.
Based on the Ordering property of binary heap, it can be of two types:

Min Heap:

In Min heap, The value of the node is greater than or equal to the value of its parent’s node. The root node is the smallest in the min-heap.

For Example 1: Using the above rules of array representation we can represent a heap in the array:

For node with value 2, its index value is 1 have left child is at (21) + 1 = 3 i.e. node with value 3 and right child is at (21) + 2 = 4 i.e. node with value 7. And we can see here that, both the children are bigger than their parent node.

Max Heap:

In Max Heap, The value of the node is smaller than or equal to the value of its parent’s node. The root node is the greatest in max Heap.

For Example 1:

For node with value 6, its index value is 1 have left child is at (21) + 1 = 3 i.e. node with value 3 and right child is at (21) + 2 = 4 i.e. node with value 2. And we can see here that, both the children are bigger than their parent node.

Now coming to the Problem, let’s discuss it with an example

The tree doesn’t follow max-heap property 9 is
smaller than 15 and 10, and 10 is smaller than 11.

Brute force Approach:

A Basic solution is to check if the root node is greater than all its descendants. After that check the same for the children of the root node.
The time and space complexity of the above approach is O(N2).

Efficient Approach:

An Efficient approach for this solution is to compare the root node with its children not with its descendants. And if the root node is greater than all its children then do the same for all the nodes, therefore, the tree is max-heap.

#include <iostream>
using namespace std;


bool isHeap(int arr[], int i, int n)
{
 
    if (i >= (n - 1) / 2)
        return true;
 
    
    if (arr[i] >= arr[2 * i + 1] &&
        arr[i] >= arr[2 * i + 2]
        && isHeap(arr, 2 * i + 1, n)
        && isHeap(arr, 2 * i + 2, n))
        return true;
 
    return false;
}
 
int main()
{
    int arr[] = { 90, 15, 10, 7, 12, 2, 7, 3 };
    int n = sizeof(arr) / sizeof(int) - 1;
 
    isHeap(arr, 0, n) ? cout<<"Yes" : cout<<"No";
 
    return 0;
}

class prepbytes
{
 
    static boolean isHeap(int arr[],
                          int i, int n)
    {
       
        if (i >= (n - 1) / 2)
        {
            return true;
        }
 
       
        if (arr[i] >= arr[2 * i + 1]
            && arr[i] >= arr[2 * i + 2]
            && isHeap(arr, 2 * i + 1, n)
            && isHeap(arr, 2 * i + 2, n))
        {
            return true;
        }
 
        return false;
    }
 
    public static void main(String[] args)
    {
        int arr[] = { 90, 15, 10, 7, 12, 2, 7, 3 };
        int n = arr.length - 1;
        if (isHeap(arr, 0, n)) {
            System.out.println("Yes");
        }
        else {
            System.out.println("No");
        }
    }
}

def isHeap(arr, i, n):
     
    if i >= int((n - 1) / 2):
        return True
   
    if(arr[i] >= arr[2 * i + 1] and
       arr[i] >= arr[2 * i + 2] and
       isHeap(arr, 2 * i + 1, n) and
       isHeap(arr, 2 * i + 2, n)):
        return True
     
    return False

if __name__ == '__main__':
    arr = [90, 15, 10, 7, 12, 2, 7, 3]
    n = len(arr) - 1
 
    if isHeap(arr, 0, n):
        print("Yes")
    else:
        print("No")

Complexity

The time complexity for the above solution is O(N).

In this article we tried to discuss How to check if a given array represents a Binary Heap. Hope this blog helps you understand the concept. To practice problems on Heap you can check out MYCODE | Competitive Programming – Heaps.