Given an array of integers, check if it represents min heap or not.
For example, the first array represents a min heap but the second array don’t, as it violates the heap property.
Since the input is an array, structural property of heap (all levels except the last level are full) cannot be violated. We only have to worry about the Min-Heap Property (priority of a node is at least as large as that of its parent) for given problem.
Since array indexing begins from 0, for a given array index i, if (2*i + 2 > n) is true then A[i] represents a leaf node. Otherwise when (2*i + 2 <= n) is true, A[i] represents internal heap node. Here, n is the size of the array.
For instance, consider array [2, 3, 4, 5, 10, 15] of size n = 6. Here [2, 3, 4] are internal nodes as (2*i + 2 <= 6) is true and [5, 10, 15] are leaf nodes as (2*i + 2 > 6) is true.
Now that we know how to differentiate between a leaf node and a internal node based on given array index and number of nodes, lets come back to the given problem.
We can efficiently solve this problem by using recursion. The idea is to start from the root node (at index 0) and check if left and right child (if any) of root node is greater than the root node or not. If yes, we recursively call the procedure for both its children else we return false from the function. Below is the complete algorithm -
- If current node is a leaf node, return true as every leaf node is a heap
- If current node is an internal node,
- Recursively check if left child is min-heap or not
- Recursively check if right child is min-heap or not (if it exists)
- Return true if both left and right child are min-heap, else return false.
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
#include <iostream> using namespace std; // Function to check if given array represents Min-Heap or not bool checkMinHeap(int A[], int i, int n) { // if i is a leaf node, return true as every leaf node is a heap if (2*i + 2 > n) return true; // if i is an internal node // recursively check if left child is heap bool left = (A[i] <= A[2*i + 1]) && checkMinHeap(A, 2*i + 1, n); // recursively check if right child is heap (to avoid array out // of bound, we first check if right child exists or not) bool right = (2*i + 2 == n) || (A[i] <= A[2*i + 2] && checkMinHeap(A, 2*i + 2, n)); // return true if both left and right child are heap return left && right; } // main function int main() { int A[] = {1, 2, 3, 4, 5, 6}; int n = sizeof(A) / sizeof(int); // start with index 0 (root of the heap) int index = 0; if (checkMinHeap(A, index, n)) cout << "Given array is a min heap"; else cout << "Given array is not a min heap"; return 0; } |
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
class HeapUtil { // Function to check if given array represents Min-Heap or not public static boolean checkMinHeap(int[] A, int i) { // if i is a leaf node, return true as every leaf node is a heap if (2*i + 2 > A.length) { return true; } // if i is an internal node // recursively check if left child is heap boolean left = (A[i] <= A[2*i + 1]) && checkMinHeap(A, 2*i + 1); // recursively check if right child is heap (to avoid array out // of bound, we first check if right child exists or not) boolean right = (2*i + 2 == A.length) || (A[i] <= A[2*i + 2] && checkMinHeap(A, 2*i + 2)); // return true if both left and right child are heap return left && right; } public static void main(String[] args) { int[] A = {1, 2, 3, 4, 5, 6}; // start with index 0 (root of the heap) int index = 0; if (checkMinHeap(A, index)) { System.out.println("Given array is a min heap"); } else { System.out.println("Given array is not a min heap"); } } } |
Output:
Given array is a min heap
Iterative C++ and Java implementation –
As recursion is costly, we can easily convert above recursive function to iterative one -
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
#include <iostream> using namespace std; // Iterative function to check if given array represents Min-Heap or not bool checkMinHeap(int A[], int n) { // check for all internal nodes that their left child and // right child (if present) holds min-heap property or not for (int i = 0; i <= (n - 2) / 2; i++) { if (A[i] > A[2 * i + 1] || ((2 * i + 2 != n) && A[i] > A[2 * i + 2])) { return false; } } return true; } // main function int main() { int A[] = { 2, 3, 5, 8, 10 }; int n = sizeof(A) / sizeof(int); if (checkMinHeap(A, n)) cout << "Given array is a min heap"; else cout << "Given array is not a min heap"; return 0; } |
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
class HeapUtil { // Iterative function to check if given array represents // Min-Heap or not public static boolean checkMinHeap(int[] A) { // check for all internal nodes that their left child and // right child (if present) holds min-heap property or not // start with index 0 (root of the heap) for (int i = 0; i <= (A.length - 2) / 2; i++) { if (A[i] > A[2 * i + 1] || ((2 * i + 2 != A.length) && A[i] > A[2 * i + 2])) { return false; } } return true; } public static void main(String[] args) { int[] A = {1, 2, 3, 4, 5, 6}; if (checkMinHeap(A)) { System.out.println("Given array is a min heap"); } else { System.out.println("Given array is not a min heap"); } } } |
Output:
Given array is a min heap
The time complexity of above solutions is O(n) and auxiliary space used by the code is O(1).
Exercise: Given an array of integers, check if it represents Max-Heap or not.
Thanks for reading.
Please use our online compiler to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
Leave a Reply
shouldn’t we check (2*i+1>n) to check if a node is a leaf node?, (2*i+2>n) will pass even if a node has just one left node
Sorry, could you please elaborate more? A left node can be a leaf… Is code failing for some input?
The base condition = if(2*i+2)>n then return true, which is checking, if node has no right node return true, my question is shouldn’t it check if the node has no left node then return true?
Could you please take another look. The condition 2*i + 2 > n checks for both left and right node.
For instance, in the example given 2*i + 2 > 6 holds true for i = 3 (a left node) and i = 4(a right node) but fails for i = 2 which is a internal node.
This code is not really work, the output is wrong
Hi, the output seems correct only. Could you please elaborate more.
I ran the recursive one and it give me “this heap is no a meanheap, meanwhile your result is a meanheap which made me confuse, i ran this code by your compiler
I think the problem is bool right = (2*i + 1 == n) ||
(A[i] <= A[2*i + 2] && checkMinHeap(A, 2*i + 2, n));
When i change 2*i+1 to 2*i+2 , it worked.
Thanks a lot for bringing this issue to our notice. The code is updated. Happy coding 🙂