Check if given array represents min heap or not

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.

  min-heap-array-1
  min-heap-example-1
 

  min-heap-array-2
  min-heap-example-2

 


 

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.

  min-heap-with-nodes-marked

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++ implementation –
 

Download   Run Code

Output:

Given array is a min heap

 

As recursion is costly, we can easily convert above recursive function to iterative one –

 
Iterative C++ implementation –
 

Download   Run Code

Output:

Given array is a min heap

 

Time complexity of above solutions is O(n).
Auxiliary space used by the program is O(1).
 

Exercise:
Given an array of integers, check if it represents Max-Heap or not.
 

Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
Sort by:   newest | oldest | most voted
Appun
Guest
Appun

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

wpDiscuz