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.
A Simple Solution is to first check root, if it’s greater than all of its descendants. Then check for children of root. Time complexity of this solution is O(n2)
An Efficient Solution is to compare root only with its children (not all descendants), if root is greater than its children and same is true for 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 (2n-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 <stdio.h> #include <limits.h> // Returns true if arr[i..n-1] represents a // max-heap bool isHeap(int arr[], int i, int n) { // If a leaf node if (i > (n - 2)/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 a leaf node if (i > (n - 2) / 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 a leaf node if i > int((n - 2) / 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 a leaf node if (i > (n - 2) / 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 a leaf node if ($i > ($n - 2) / 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 ?> |
Output:
Yes
Time complexity of this solution is O(n). The solution is similar to preorder traversal of Binary Tree.
Thanks to Utkarsh Trivedi for suggesting the above solution.
An Iterative Solution is to traverse all internal nodes and check id 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 ?> |
Output:
Yes
Thanks to Himanshu for suggesting this solution.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above
leave a comment
0 Comments