Testing if array is heap

This method tests an array of integers satisfies to see if its a max binary heap. This means

• each node is greater than or equal to it's children

• each node has at most 2 children

• the leaf nodes are filled from left to right

This is for heaps that do not use element 0. See here.

/*returns true if array satisfies heap property for heap from [START, END]*/  
private boolean isHeap(final int[] heap, final int START, final int END) {  
    for(int i = START; i <= Math.ceil(END / 2); i++) {  
       if(2 * i + 1 <= END && heap[i] < heap[2 * i + 1])  
               return false;  
       else if(2 * i <= END && heap[i] < heap[2 * i])  
               return false;  
   }  

   return true;  

}

You code loops through the possible parents and checks the heap invariant for both children. This is a little messy: you have a special case for odd-number heaps, and you have two different conditions to check.

How about we loop through the possible children instead?

private boolean isHeap(final int[] heap, final int start, final int end) {
for (int i = start + 1; i heap[i/2]) {
return false;
}
}
return true;
}


StackExchange Code Review Q#136048, answer score: 5