![\"\"](\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1655875432538-Article.jpg\")
<\/p>\n<\/p>\n
Given an array of integers, how We have to check if the given array represents a binary max-heap or not.<\/p>\n
First, we\u2019ll see what is Binary heaps and its types<\/p>\n
A Binary Heap is a complete binary tree that follows a heap ordering property. The representation is done as:<\/p>\n
The above table shows the indexes of the ith<\/sup> node. In Min heap, The value of the node is greater than or equal to the value of its parent\u2019s node. The root node is the smallest in the min-heap.<\/p>\n For Example 1:<\/em><\/strong> Using the above rules of array representation we can represent a heap in the array:<\/p>\n 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 (2<\/em>1) + 2 = 4 i.e. node with value 7. And we can see here that, both the children are bigger than their parent node.<\/p>\n In Max Heap, The value of the node is smaller than or equal to the value of its parent\u2019s node. The root node is the greatest in max Heap.<\/p>\n For Example 1:<\/em><\/strong><\/p>\n 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 (2<\/em>1) + 2 = 4 i.e. node with value 2. And we can see here that, both the children are bigger than their parent node.<\/p>\n Now coming to the Problem, let’s discuss it with an example<\/p>\n The tree doesn’t follow max-heap property 9 is 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. 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.<\/p>\n\t\t\t\t\t\t
\nBased on the Ordering property of binary heap, it can be of two types:<\/p>\nMin Heap:<\/h3>\n
![\"\"](\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1656502371830-Image-02.png\")
<\/p>\nMax Heap:<\/h3>\n
![\"\"](\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1656505001174-Image-02%20%281%29.png\")
<\/p>\n![\"\"](\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1655875545496-Image-01%20%282%29.png\")
<\/p>\n
\nsmaller than 15 and 10, and 10 is smaller than 11.<\/p>\n<\/p>\nBrute force Approach:<\/h3>\n
\nThe time and space complexity of the above approach is O(N2).<\/p>\nEfficient Approach:<\/h3>\n