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

Last Updated : 15 Dec, 2022

Given an array, how to check if the given array represents a Binary Max-Heap.
Examples:

Input:  arr[] = {90, 15, 10, 7, 12, 2} 
Output: True
The given array represents below tree
       90
     /    \
   15      10
  /  \     /
 7    12  2 
The tree follows max-heap property as every
node is greater than all of its descendants.

Input:  arr[] = {9, 15, 10, 7, 12, 11} 
Output: False
The given array represents below tree
       9
     /    \
   15      10
  /  \     /
 7    12  11
The tree doesn't follows max-heap property 9 is 
smaller than 15 and 10, and 10 is smaller than 11.

Recommended PracticeDoes array represent HeapTry It!

A Simple Solution is to first check root if it’s greater than all of its descendants. Then check for children of the root. Time complexity of this solution is O(n²)

An Efficient Solution is to compare root only with its children (not all descendants), if root is greater than its children and the same is true for all nodes, then tree is max-heap (This conclusion is based on transitive property of > operator, i.e., if x > y and y > z, then x > z).
The last internal node is present at index (n-2)/2 assuming that indexing begins with 0.

Below is the implementation of this solution.

C++

// C program to check whether a given array 
// represents a max-heap or not 
#include <limits.h> 
#include <stdio.h> 
  
// Returns true if arr[i..n-1] represents a 
// max-heap 
bool isHeap(int arr[], int i, int n) 
{ 
    // If (2 * i) + 1 >= n, then leaf node, so return true 
    if (i >= (n - 1) / 2) 
        return true; 
  
    // If an internal node and is  
    // greater than its children, 
    // and same is recursively  
    // true for the children 
    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; 
} 
  
// Driver program 
int main() 
{ 
    int arr[] = { 90, 15, 10, 7, 12, 2, 7, 3 }; 
    int n = sizeof(arr) / sizeof(int) - 1; 
  
    isHeap(arr, 0, n) ? printf("Yes") : printf("No"); 
  
    return 0; 
}

Java

// Java program to check whether a given array 
// represents a max-heap or not 
class GFG  
{ 
  
    // Returns true if arr[i..n-1]  
    // represents a max-heap 
    static boolean isHeap(int arr[],  
                          int i, int n) 
    { 
        // If (2 * i) + 1 >= n, then leaf node, so return true 
        if (i >= (n - 1) / 2)  
        { 
            return true; 
        } 
  
        // If an internal node and  
        // is greater than its 
        // children, and same is  
        // recursively true for the 
        // children 
        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; 
    } 
  
    // Driver program 
    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"); 
        } 
    } 
} 
  
// This code contributed by 29AjayKumar

Python3

# Python3 program to check whether a  
# given array represents a max-heap or not  
  
# Returns true if arr[i..n-1]  
# represents a max-heap  
def isHeap(arr, i, n): 
      
    # If (2 * i) + 1 >= n, then leaf node, so return true 
    if i >= int((n - 1) / 2):  
        return True
      
    # If an internal node and is greater  
    # than its children, and same is 
    # recursively true for the children  
    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
  
# Driver Code 
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") 
  
# This code is contributed by PranchalK 

C#

// C# program to check whether a given   
// array represents a max-heap or not 
using System; 
  
class GFG 
{ 
  
// Returns true if arr[i..n-1] represents a  
// max-heap  
static bool isHeap(int []arr, int i, int n)  
{ 
    // If (2 * i) + 1 >= n, then leaf node, so return true 
    if (i >= (n - 1) / 2)  
    { 
        return true; 
    } 
  
    // If an internal node and is greater  
    // than its children, and same is  
    // recursively true for the children  
    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; 
} 
  
// Driver Code  
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)) 
    { 
        Console.Write("Yes"); 
    }  
      
    else
    { 
        Console.Write("No"); 
    } 
} 
} 

PHP

<?php 
// PHP program to check whether a given  
// array represents a max-heap or not 
  
// Returns true if arr[i..n-1]  
// represents a max-heap 
function isHeap($arr, $i, $n) 
{ 
      
// If (2 * i) + 1 >= n, then leaf node, so return true 
if ($i >= ($n - 1) / 2) 
    return true; 
  
// If an internal node and is greater  
// than its children, and same is  
// recursively true for the children 
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; 
} 
  
// Driver Code 
$arr = array(90, 15, 10, 7, 12, 2, 7, 3); 
$n = sizeof($arr); 
  
if(isHeap($arr, 0, $n)) 
    echo "Yes"; 
else
    echo "No"; 
  
// This code is contributed  
// by Akanksha Rai 
?> 

Javascript

<script> 
// Javascript program to check whether a given array 
// represents a max-heap or not 
  
// Returns true if arr[i..n-1] 
    // represents a max-heap 
function isHeap(arr,i,n) 
{ 
    // If (2 * i) + 1 >= n, then leaf node, so return true 
        if (i >= (n - 1) / 2) 
        { 
            return true; 
        } 
   
        // If an internal node and 
        // is greater than its 
        // children, and same is 
        // recursively true for the 
        // children 
        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; 
} 
  
// Driver program 
let arr=[ 90, 15, 10, 7, 12, 2, 7, 3 ]; 
let n = arr.length - 1; 
if (isHeap(arr, 0, n)) { 
    document.write("Yes<br>"); 
} 
else { 
    document.write("No<br>"); 
} 
  
  
// This code is contributed by rag2127 
</script> 

Output

Yes

Time complexity: O(n)
Auxiliary Space: O(h), Here h is the height of the given tree and the extra space is used due to the recursion call stack.

An Iterative Solution is to traverse all internal nodes and check id the node is greater than its children or not.

C++

// C program to check whether a given array 
// represents a max-heap or not 
#include <stdio.h> 
#include <limits.h> 
  
// Returns true if arr[i..n-1] represents a 
// max-heap 
bool isHeap(int arr[],  int n) 
{ 
    // Start from root and go till the last internal 
    // node 
    for (int i=0; i<=(n-2)/2; i++) 
    { 
        // If left child is greater, return false 
        if (arr[2*i +1] > arr[i]) 
                return false; 
  
        // If right child is greater, return false 
        if (2*i+2 < n && arr[2*i+2] > arr[i]) 
                return false; 
    } 
    return true; 
} 
  
// Driver program 
int main() 
{ 
    int arr[] = {90, 15, 10, 7, 12, 2, 7, 3}; 
    int n = sizeof(arr) / sizeof(int); 
  
    isHeap(arr, n)? printf("Yes"): printf("No"); 
  
    return 0; 
} 

Java

// Java program to check whether a given array  
// represents a max-heap or not 
  
class GFG { 
  
// Returns true if arr[i..n-1] represents a  
// max-heap  
    static boolean isHeap(int arr[], int n) { 
        // Start from root and go till the last internal  
        // node  
        for (int i = 0; i <= (n - 2) / 2; i++) { 
            // If left child is greater, return false  
            if (arr[2 * i + 1] > arr[i]) { 
                return false; 
            } 
  
            // If right child is greater, return false  
            if (2 * i + 2 < n && arr[2 * i + 2] > arr[i]) { 
                return false; 
            } 
        } 
        return true; 
    } 
  
// Driver program  
    public static void main(String[] args) { 
        int arr[] = {90, 15, 10, 7, 12, 2, 7, 3}; 
        int n = arr.length; 
        if (isHeap(arr, n)) { 
            System.out.println("Yes"); 
        } else { 
            System.out.println("No"); 
        } 
    } 
} 
// This code is contributed by 29AjayKumar 

Python3

# Python3 program to check whether a  
# given array represents a max-heap or not  
  
# Returns true if arr[i..n-1]  
# represents a max-heap  
def isHeap(arr, n): 
      
    # Start from root and go till  
    # the last internal node 
    for i in range(int((n - 2) / 2) + 1): 
          
        # If left child is greater,  
        # return false  
        if arr[2 * i + 1] > arr[i]:  
                return False
  
        # If right child is greater, 
        # return false  
        if (2 * i + 2 < n and
            arr[2 * i + 2] > arr[i]):  
                return False
    return True
  
# Driver Code 
if __name__ == '__main__': 
    arr = [90, 15, 10, 7, 12, 2, 7, 3]  
    n = len(arr) 
  
    if isHeap(arr, n): 
        print("Yes") 
    else: 
        print("No") 
          
# This code is contributed by PranchalK 

C#

// C# program to check whether a given array  
// represents a max-heap or not  
using System; 
  
class GFG  
{ 
  
// Returns true if arr[i..n-1]  
// represents a max-heap  
static bool isHeap(int []arr, int n) 
{  
    // Start from root and go till  
    // the last internal node  
    for (int i = 0; i <= (n - 2) / 2; i++)  
    {  
        // If left child is greater,  
        // return false  
        if (arr[2 * i + 1] > arr[i]) 
        {  
            return false;  
        }  
  
        // If right child is greater,  
        // return false  
        if (2 * i + 2 < n && arr[2 * i + 2] > arr[i])  
        {  
            return false;  
        }  
    }  
    return true;  
}  
  
// Driver Code  
public static void Main()  
{  
    int []arr = {90, 15, 10, 7, 12, 2, 7, 3};  
    int n = arr.Length;  
    if (isHeap(arr, n)) 
    {  
        Console.Write("Yes");  
    }  
    else 
    {  
        Console.Write("No");  
    }  
}  
}  
  
// This code is contributed  
// by 29AjayKumar 

PHP

<?php 
// PHP program to check whether a  
// given array represents a max-heap or not  
  
// Returns true if arr[i..n-1]  
// represents a max-heap  
function isHeap($arr, $i, $n)  
{ 
    // Start from root and go till  
    // the last internal node  
    for ($i = 0; $i < (($n - 2) / 2) + 1; $i++)  
    { 
        // If left child is greater,  
        // return false  
        if($arr[2 * $i + 1] > $arr[$i])  
                return False; 
  
        // If right child is greater,  
        // return false  
        if (2 * $i + 2 < $n &&  
                $arr[2 * $i + 2] > $arr[$i]) 
                return False; 
      
    return True; 
    } 
} 
  
// Driver Code  
$arr = array(90, 15, 10, 7, 12, 2, 7, 3);  
$n = sizeof($arr);  
  
if(isHeap($arr, 0, $n))  
    echo "Yes";  
else
    echo "No"; 
      
// This code is contributed by Princi Singh 
?> 

Javascript

<script> 
  
// Javascript program to check 
// whether a given array 
// represents a max-heap or not 
  
// Returns true if arr[i..n-1]  
// represents a max-heap 
function isHeap( arr, n) 
{ 
    // Start from root and go till  
    // the last internal node 
    for (let i=0; i<=Math.floor((n-2)/2); i++) 
    { 
        // If left child is greater,  
        // return false 
        if (arr[2*i +1] > arr[i]) 
                return false; 
  
        // If right child is greater, 
        // return false 
        if (2*i+2 < n && arr[2*i+2] > arr[i]) 
                return false; 
    } 
    return true; 
} 
    // driver code  
      
    let arr = [90, 15, 10, 7, 12, 2, 7, 3]; 
    let n = arr.length; 
    if (isHeap(arr, n)) { 
        document.write("Yes"); 
        }  
    else { 
        document.write("No"); 
        } 
      
</script>

Output

Yes

Time complexity: O(n), Where n is the total number of elements in the given array.
Auxiliary Space: O(1), As constant extra space is used.

Thanks to Himanshu for suggesting this solution.

GeeksforGeeks

Improve

Previous Article

Check if a given Binary Tree is a Heap

Iterative HeapSort

Similar Reads

Difference between Binary Heap, Binomial Heap and Fibonacci Heap

Binary Heap:A Binary Heap is a Binary Tree with following properties. It’s a complete binary tree i.e., all levels are completely filled except possibly the last level and the last level has all keys as left as possible. This property of Binary Heap makes them suitable to be stored in an array. A Binary Heap is either Min Heap or Max Heap. In a Min

Check if an array represents Inorder of Binary Search tree or not

Given an array of N element. The task is to check if it is Inorder traversal of any Binary Search Tree or not. Print "Yes" if it is Inorder traversal of any Binary Search Tree else print "No". Examples: Input : arr[] = { 19, 23, 25, 30, 45 } Output : Yes Input : arr[] = { 19, 23, 30, 25, 45 } Output : NoRecommended PracticeInorder Traversal and BST

Check if an encoding represents a unique binary string

Given an encoding of a binary string of length k, the task is to find if the given encoding uniquely identifies a binary string or not. The encoding has counts of contiguous 1s (separated by 0s). For example, encoding of 11111 is {5}, encoding of 01101010 is {2, 1, 1} and encoding of 111011 is {3, 2}. Examples : Input: encoding[] = {3, 3, 3} Length

Check if the given graph represents a Bus Topology

Given a graph G, check if it represents a Bus Topology.A Bus Topology is the one shown in the image below: Examples: Input: Output: YES Input: Output: NO A graph of V vertices represents a bus topology if it satisfies the following two conditions: Each node except the starting end ending ones has degree 2 while the starting and ending have degree 1

Check if the given graph represents a Star Topology

Given a graph G, the task is to check if it represents a Star Topology.A Star Topology is the one shown in the image below: Examples: Input : Graph = Output : YES Input : Graph = Output : NO A graph of V vertices represents a star topology if it satisfies the following three conditions: One node (also called the central node) has degree V - 1.All n

Check if the given graph represents a Ring Topology

Given a graph G, the task is to check if it represents a Ring Topology.A Ring Topology is the one shown in the image below: Examples: Input : Graph = Output : YES Input : Graph = Output : NO A graph of V vertices represents a Ring topology if it satisfies the following three conditions: Number of vertices >= 3.All vertices should have degree 2.N

Check if given path between two nodes of a graph represents a shortest paths

Given an unweighted directed graph and Q queries consisting of sequences of traversal between two nodes of the graph, the task is to find out if the sequences represent one of the shortest paths between the two nodes.Examples: Input: 1 2 3 4 Output: NOExplanation: The first and last node of the input sequence is 1 and 4 respectively. The shortest p

Check whether Array represents a Fibonacci Series or not

Given an array arr[] consisting of N integers, the task is to check whether a Fibonacci series can be formed using all the array elements or not. If possible, print "Yes". Otherwise, print "No". Examples: Input: arr[] = { 8, 3, 5, 13 } Output: Yes Explanation: Rearrange given array as {3, 5, 8, 13} and these numbers form Fibonacci series. Input: ar

Sorted order printing of a given array that represents a BST

Given an array that stores a complete Binary Search Tree, write a function that efficiently prints the given array in ascending order. For example, given an array [4, 2, 5, 1, 3], the function should print 1, 2, 3, 4, 5 Solution: Inorder traversal of BST prints it in ascending order. The only trick is to modify recursion termination condition in st

Minimum steps required to convert X to Y where a binary matrix represents the possible conversions

Given a binary matrix of size NxN where 1 denotes that the number i can be converted to j, and 0 denotes it cannot be converted to. Also given are two numbers X(<N)and Y(<N), the task is to find the minimum number of steps required to convert the number X to Y. If there is no such way possible, print -1. Examples: Input: {{ 0, 0, 0, 0, 0, 0,

Article Tags :

Practice Tags :