Problem : You have given an array of integer, check if the given array represents a binary max-heap data structure. In max heap every node is greater than all of its descendants.
For example :
Input: array[] = {100, 25, 20, 17, 22, 12}
Output: true
The given array represents below tree
100
/ \
25 20
/ \ /
17 22 12
This binary tree follows max-heap property as every node is greater than all of its descendant.
Input: array[] = {19, 25, 20, 17, 22, 21}
Output: false
This array represents following tree :
19
/ \
25 20
/ \ /
17 22 21
This tree violates max-heap property as root 19 is less than 25 and 20, and 20 is smaller than 21.
Solution :
The brute force solution of this problem is first to check if root is greater than all of its descendants and then subsequently check for all children of root. Time complexity of this solution is O(n^2) because for each node you check every other node.
You can optimize your solution by only comparing root with its children and not with all descendants. If root is greater than its children and same is true for all nodes then tree is a max-heap. This solution is similar to preorder traversal of binary tree because there also we compare root, left and right node.
Here is a Java solution of problem, how to check if a given array is binary max heap or not :
/**
* Returns true if given array is a binary max-heap. false otherwise
*
* @input[] - given array
* @i - start index
* @length - length of array
*/
public static boolean isBinaryMaxHeap(int i, int[] tree) {
// Base case
if (i >= tree.length - 1)
return true;
// If root is greater than its children and
// same is recursively true for all the children, then tree is binary
// max heap
int ROOT = i;
int LEFT_CHILD = 2 * i + 1;
int RIGHT_CHILD = 2 * i + 2;
if (valueOf(ROOT, tree) > valueOf(LEFT_CHILD, tree)
&& valueOf(ROOT, tree) >= valueOf(RIGHT_CHILD, tree)
&& isBinaryMaxHeap(LEFT_CHILD, tree)
&& isBinaryMaxHeap(RIGHT_CHILD, tree)) {
return true;
}
return false;
}
Time Complexity of this solution is O(n) because we only check 2 other nodes for each node.
