Algorithm for checking if an Array with n-elements is a minimum heap

Question

I'm trying to outline an algorithm to determine if my array is a minimum heap. Is there any documentation out there that could help me with this? I found a function for it on Apache's website, but it doesn't show exactly how the function works; just that there exists a function (BinaryHeap(boolean isMinHeap)).

Vicariate

Answer 1

The Wikipedia article should help you.

Here are some questions to get you thinking about the solution:

1. What must be true about the root of a heap, assuming the heap is a min heap?
2. If the root of the heap satisfies the min heap property, how do you ensure that the subtrees of the root also hold the property?
3. What if the root of the tree has no children? Is it a min heap?

Vela

Answer 2

I think this will work !

bool checkminheap(int arr[],root)
{
     if(root>=sizeof(arr)/sizeof(arr[0])-1)
         return 1;
     if(arr[root]>arr[2*root] || arr[root]>arr[2*root+1])  //check root is the smallest element
      return 0; 
    if(!checkminheap(arr,2*root))//check leftsubtree
      return 0;
    if(!checkminheap(arr,2*root+1))//check rightsubtree
      return 0;

     return 1;
}  

Chengteh

Answer 3

Adding a verbose solution with java generics support, it is relatively easier to follow.

public static <T extends Comparable<T>> boolean isMinHeap(T arr[], int rootIndex) {
  boolean isMaxH = true;
  int lChild = 2 * rootIndex + 1;
  int rChild = 2 * rootIndex + 2;

  // Nothing to compare here, as lChild itself is larger then arr length.
  if (lChild >= arr.length) {
    return true;
  }

  if (arr[rootIndex].compareTo(arr[lChild]) > 0) {
    return false;
  } else {
    isMaxH = isMaxH && isMinHeap(arr, lChild);
  }

  // rChild comparison not needed, return the current state of this root.
  if (rChild >= arr.length) {
    return isMaxH;
  }

  if (arr[rootIndex].compareTo(arr[rChild]) > 0) {
    return false;
  } else {
    isMaxH = isMaxH && isMinHeap(arr, rChild);
  }

  return isMaxH;
}

Holleyholli