Check If a Given Array Represents Min Heap or Not

A Heap is a Tree-based data structure in which the tree is a complete binary tree. Binary heap is of two types max heap and min heap. A min-heap is a tree-like structure in which the value of the parent node should always be less than both of its left and right child and follow this property recursively for all nodes until it reaches to leaf node. According to this property, the root node of the min-heap has the smallest value. In this article, we are going to check whether an array represents a min-heap or not.

Problem Description

We are given an array, we have to check whether it represents a min-heap or not.

Examples

Input

int array[] = {10,15,30,40,50,100,40}

Output

yes

Input

int array[] = {20,15,8,10,5,7,6,2,9,1}

Output

No

Approach

In this approach, we will traverse the whole array and check for each node whether its value is smaller than both of its child. If we reach the end of the array then return true else return false. The left child is represented by 2*i +1 and the right child is represented by 2*i +2 in an array.

Steps for Implementation

Follow the below steps to implement the solution ?

Step 1: Start from the root node and traverse the whole array.

Step 2: If the left child is greater than the root node then return true.

Step 3: If the right child is greater than the root node then return true.

Step 4: If both the above conditions are true then return true else return false.

C++ Implementation

Let's implement the solution using C++.

#include<bits/stdc++.h>
using namespace std;

bool isHeap(int arr[], int n)
{
// Start from the root and traverse the whole array
    for (int i=0; i<=(n-2)/2; i++) {
// If left child is smaller, return false
        if (arr[2*i +1] < arr[i])
            return false;
// If right child is smaller, return false
        if (arr[2*i+2] < arr[i])
            return false;
    }
// Return true if move out of the loop
    return true;
}
int main()
{
    int arr[] = {10,15,30,40,50,100,40};
    int n = 7 ;
// print true if the given array represents min-heap else false
    isHeap(arr, n) ? cout << "True" : cout << "False";
    return 0;
}

Output

The above program code will produce the following result ?

True

Java Implementation

Let's implement the solution using Java.

import java.util.*;

public class Main {

    public static boolean isHeap(int[] arr, int n) {
        // Start from the root and traverse the whole array
        for (int i = 0; i <= (n - 2) / 2; i++) {
            // If left child is smaller, return false
            if (2 * i + 1 < n && arr[2 * i + 1] < arr[i]) {
                return false;
            }

            // If right child is smaller, return false
            if (2 * i + 2 < n && arr[2 * i + 2] < arr[i]) {
                return false;
            }
        }
        // Return true if we exit the loop
        return true;
    }

    public static void main(String[] args) {
        int[] arr = {10, 15, 30, 40, 50, 100, 40};
        int n = 7;

        // Print true if the given array represents min-heap, else false
        if (isHeap(arr, n)) {
            System.out.println("True");
        } else {
            System.out.println("False");
        }
    }
}

Output

The above program code will produce the following result ?

True

Python Implementation

Let's implement the solution using Python.

def isHeap(arr, n):
    # Start from the root and traverse the whole array
    for i in range((n - 2) // 2 + 1):
        # If left child is smaller, return False
        if 2 * i + 1 < n and arr[2 * i + 1] < arr[i]:
            return False
        
        # If right child is smaller, return False
        if 2 * i + 2 < n and arr[2 * i + 2] < arr[i]:
            return False
            
    # Return True if we exit the loop
    return True

if __name__ == "__main__":
    arr = [10, 15, 30, 40, 50, 100, 40]
    n = 7

    # Print true if the given array represents min-heap, else false
    if isHeap(arr, n):
        print("True")
    else:
        print("False")

Output

The above program code will produce the following result ?

True

Time complexity: O(n), as we are traversing the array.

Space complexity: O(1), constant space.