Problem Link : Does array represent Heap [GeeksforGeeks]
Problem Description : Does array represent Heap
Given an array arr of size n, the task is to check if the given array can be a level order representation of a Max Heap.
Example 1:
Input:
n = 6
arr[] = {90, 15, 10, 7, 12, 2}
Output:
1
Explanation:
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.
Example 2:
Input:
n = 6
arr[] = {9, 15, 10, 7, 12, 11}
Output:
0
Explanation:
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.
Your Task:
You don’t need to read input or print anything. Your task is to complete the function isMaxHeap() which takes the array arr[] and its size n as inputs and returns True if the given array could represent a valid level order representation of a Max Heap, or else, it will return False.
Expected Time Complexity: O(n)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ n ≤ 105
1 ≤ arri ≤ 105
Solution :
1. Understanding the Max Heap Property:
Before diving into the code, it’s crucial to understand the Max Heap property. In a Max Heap, every node should be greater than or equal to its children. This property is maintained for all nodes in the heap.
2. Iterating through the Nodes:
The countSub method iterates through the nodes of the heap. It starts from the last non-leaf node and moves towards the root. This ensures that every node and its descendants are checked in a bottom-up fashion.
3. Checking Max Heap Property for a Node:
The isHeapPropertySatisfied method checks whether the Max Heap property is satisfied for a given node and its descendants. It checks the left and right children, ensuring they are within array bounds and greater than the current node.
4. Putting It All Together:
By combining the loop in countSub and the recursive checks in isHeapPropertySatisfied, the code effectively examines each node and its descendants. If, at any point, the Max Heap property is violated, the method returns false. Otherwise, it returns true.
Conclusion:
Understanding the Max Heap property and the bottom-up approach to check it helps in grasping the provided solution. The code efficiently validates whether the given array could represent a valid level order representation of a Max Heap or not.
Code :
class Solution {
public boolean countSub(long arr[], long n)
{
for (long i = (n – 2) / 2; i >= 0; i–) {
if (!isHeapPropertySatisfied(arr, i, n)) {
return false;
}
}
return true;
}
public boolean isHeapPropertySatisfied(long arr[], long i, long n) {
// Check if the left child is within the array and greater than the parent
if (2 * i + 1 < n && arr[(int)(2 * i + 1)] > arr[(int)i]) {
return false;
}
// Check if the right child is within the array and greater than the parent
if (2 * i + 2 < n && arr[(int)(2 * i + 2)] > arr[(int)i]) {
return false;
}
return true;
}
}
#include <iostream>
#include <vector>
class Solution {
public:
bool countSub(std::vector<long>& arr, long n) {
for (long i = (n – 2) / 2; i >= 0; i–) {
if (!isHeapPropertySatisfied(arr, i, n)) {
return false;
}
}
return true;
}
bool isHeapPropertySatisfied(std::vector<long>& arr, long i, long n) {
// Check if the left child is within the array and greater than the parent
if (2 * i + 1 < n && arr[2 * i + 1] > arr[i]) {
return false;
}
// Check if the right child is within the array and greater than the parent
if (2 * i + 2 < n && arr[2 * i + 2] > arr[i]) {
return false;
}
return true;
}
};
int main() {
// Example usage
Solution sol;
std::vector<long> arr = {90, 15, 10, 7, 12, 2};
long n = arr.size();
bool result = sol.countSub(arr, n);
std::cout << (result ? “True” : “False”) << std::endl;
return 0;
}
class Solution:
def countSub(self, arr, n):
for i in range((n – 2) // 2, -1, -1):
if not self.isHeapPropertySatisfied(arr, i, n):
return False
return True
def isHeapPropertySatisfied(self, arr, i, n):
# Check if the left child is within the array and greater than the parent
if 2 * i + 1 < n and arr[2 * i + 1] > arr[i]:
return False
# Check if the right child is within the array and greater than the parent
if 2 * i + 2 < n and arr[2 * i + 2] > arr[i]:
return False
return True
# Example usage
sol = Solution()
arr = [90, 15, 10, 7, 12, 2]
n = len(arr)
result = sol.countSub(arr, n)
print(result)
Output :
Output: 1
