Given an array of integers nums. Check whether the array represents a binary min-heap or not. Return true if it does, otherwise return false.
A binary min-heap is a complete binary tree where the key at the root is the minimum among all keys present in a binary min-heap and the same property is recursively true for all nodes in a Binary Tree.
Input: nums = [10, 20, 30, 21, 23]
Output: true
Explanation: Each node has a lower or equal value than its children.
Input: nums = [10, 20, 30, 25, 15]
Output: false
Explanation: The node with value 20 has a child with value 15, thus it is not a min-heap.
Input: nums = [1, 2, 1, 3]
To check if the given array represents a min-heap, all the nodes must follow the min-heap property.
Min-Heap Property: Each node value must be smaller than the value of its immediate left and right children node.
Since the leaf-nodes have no children, directly checking the min-heap property for the non-leaf nodes will be enough to check if the array represents a min heap.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Function to check if the given array is a min-heap
bool isHeap(vector<int>& nums) {
int n = nums.size(); // Size of the array
// Iterate on the non-leaf nodes from the back
for(int i = n/2 -1; i >= 0; i--) {
int leftChildInd = 2*i + 1;
int rightChildInd = 2*i + 2;
// If left child has a smaller value than the parent
if(leftChildInd < n && nums[leftChildInd] < nums[i])
return false;
// If right child has a smaller value than parent
if(rightChildInd < n && nums[rightChildInd] < nums[i])
return false;
}
return true;
}
};
// Driver code
int main() {
vector<int> nums = {10, 20, 30, 21, 23};
cout << "Given Array: ";
for(int x : nums) cout << x << " ";
// Creating an object of the Solution class
Solution sol;
// Function call to check if the given array is a min-heap
bool ans = sol.isHeap(nums);
if(ans) cout << "\nThe given array is a min-heap.";
else cout << "\nThe given array is not a min-heap.";
return 0;
}
import java.util.*;
class Solution {
// Function to check if the given array is a min-heap
public boolean isHeap(int[] nums) {
int n = nums.length; // Size of the array
// Iterate on the non-leaf nodes from the back
for(int i = n/2 - 1; i >= 0; i--) {
int leftChildInd = 2 * i + 1;
int rightChildInd = 2 * i + 2;
// If left child has a smaller value than the parent
if(leftChildInd < n && nums[leftChildInd] < nums[i])
return false;
// If right child has a smaller value than parent
if(rightChildInd < n && nums[rightChildInd] < nums[i])
return false;
}
return true;
}
}
class Main {
public static void main(String[] args) {
int[] nums = {10, 20, 30, 21, 23};
System.out.print("Given Array: ");
for(int x : nums) {
System.out.print(x + " ");
}
// Creating an object of the Solution class
Solution sol = new Solution();
// Function call to check if the given array is a min-heap
boolean ans = sol.isHeap(nums);
if(ans)
System.out.println("\nThe given array is a min-heap.");
else
System.out.println("\nThe given array is not a min-heap.");
}
}
class Solution:
# Function to check if the given array is a min-heap
def isHeap(self, nums):
n = len(nums) # Size of the array
# Iterate on the non-leaf nodes from the back
for i in range(n//2 - 1, -1, -1):
leftChildInd = 2*i + 1
rightChildInd = 2*i + 2
# If left child has a smaller value than the parent
if leftChildInd < n and nums[leftChildInd] < nums[i]:
return False
# If right child has a smaller value than parent
if rightChildInd < n and nums[rightChildInd] < nums[i]:
return False
return True
def main():
nums = [10, 20, 30, 21, 23]
print("Given Array: ", end="")
for x in nums:
print(x, end=" ")
# Creating an object of the Solution class
sol = Solution()
# Function call to check if the given array is a min-heap
ans = sol.isHeap(nums)
if ans:
print("\nThe given array is a min-heap.")
else:
print("\nThe given array is not a min-heap.")
if __name__ == "__main__":
main()
class Solution {
// Function to check if the given array is a min-heap
isHeap(nums) {
let n = nums.length; // Size of the array
// Iterate on the non-leaf nodes from the back
for(let i = Math.floor(n/2) - 1; i >= 0; i--) {
let leftChildInd = 2*i + 1;
let rightChildInd = 2*i + 2;
// If left child has a smaller value than the parent
if(leftChildInd < n && nums[leftChildInd] < nums[i]) {
return false;
}
// If right child has a smaller value than parent
if(rightChildInd < n && nums[rightChildInd] < nums[i]) {
return false;
}
}
return true;
}
}
// Driver code
function main() {
let nums = [10, 20, 30, 21, 23];
process.stdout.write("Given Array: ");
for(let x of nums) {
process.stdout.write(x + " ");
}
// Creating an object of the Solution class
let sol = new Solution();
// Function call to check if the given array is a min-heap
let ans = sol.isHeap(nums);
if(ans) {
process.stdout.write("\nThe given array is a min-heap.");
} else {
process.stdout.write("\nThe given array is not a min-heap.");
}
}
// Run the driver code
main();
Time Complexity: O(N) (where N represents the number of elements in the array)
Iterating on all the non-leaf nodes will take N/2 iterations which is of the order of O(N) (Constant factors like 1/2 are ignored while following the Big-O notation).
Space Complexity: O(1), as there is no extra space used.
Q: Why do we only check parent-child relations (nums[i] ≤ nums[2*i+1])?
A: A heap does not require total sorting. It only needs each parent ≤ its children.
Q: How is this different from a binary search tree (BST)?
A: BST: Left subtree < root < right subtree (strict ordering). Heap: Only requires parent ≤ children, not full ordering.
Q: How would you check if an array represents a max-heap instead of a min-heap?
A: Instead of nums[i] ≤ nums[child], check nums[i] ≥ nums[child].