Algorithm to check if an array with n-elements is a minimal heap

Question

I am trying to describe an algorithm to determine if my array is a minimal heap. Is there any documentation that could help me with this? I found a function for it on the Apache website, but it does not show exactly how this function works; there just exists a function (BinaryHeap (boolean isMinHeap)).

Answer 1

The Wikipedia article should help you.

Here are some questions to help you think about a solution:

• What should be true about the heap root if the heap is a bunch of minutes?
• If the heap root satisfies the minimum heap property, how do you guarantee that the root subtrees also retain the property?
• What if the root of the tree has no children? Is this a small pile?

Answer 2

I think it 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; } 

Answer 3

Adding a detailed solution with support for java generics is relatively easy 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; }