Testing if array is heap

Question

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

1. each node is greater than or equal to it's children
2. each node has at most 2 children
3. 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; 
} 

• Pimgd: What's broken about this?
• kidinme12: @Pimgd nothing. I'm just asking if there's a better way to tell if something's a heap. I thought broken code is off topic on this site?
• Tunaki: @Pimgd heap is not an array, it is declared as final int heap.

Answer 1

Possible bug

The method isHeap takes an array along with a start and end index. Although the code does try to take into account potential out of bounds by checking 2 * i + 1 <= end and 2 * i <= end, there is no check that end is strictly lower than heap.length. As such, out of bounds array indexes can still occur:

isHeapReview(new int[] { 0 }, 0, 1);

would throw an java.lang.ArrayIndexOutOfBoundsException: 1. There are multiple solutions depending on the intended usage of the method:

• You can defend from such a case by re-defining end to be the minimum of the given end and heap.length - 1 with Math.min(end, heap.length - 1).
• You can check if end is greater or equal than heap.length and, if true, throw an IllegalArgumentException.

In the same way, there is no check that start is a positive integer. Those checks should be added to it too.

Code style

Watch out your indentation style and braces. The following

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; 

doesn't use curly braces and is not indented properly. Even if they are redundant, it is best to explicitely add the curly braces, as they prevent future possible issues. Use this style instead:

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;
}

where the braces were added, indentation is fixed, spaces are added after if; all of this contribute to easier to read code.

Simplification

end / 2 performs integer division and will return an integer, so invoking Math.ceil on it will have no effect. You can remove it; the code already loops from 0 to end / 2 inclusive.

Also, since end is expected to be lower or equal than heap.length - 1, you can remove the 2 * i <= END check in:

if (2 * i <= END && heap[i] < heap[2 * i])

This will always be true since i maximal value is end / 2.

With this change, you can even refactor the if statement to:

if (2 * i + 1 <= END && heap[i] < heap[2 * i + 1] || heap[i] < heap[2 * i]) {
 return false;
}

without the need of an else if statement. It does make the line a tiny bit longer, but it is short enough to typically fit on a screen and is pretty direct.

Namings

Don't write the parameters in upper-case; only use this for constants. START should really be start; in the same way, END should be end.

• kidinme12: Couple questions about naming. START and END are declared with final so they are constant. Should they still be lowercase because their parameters? I didn't make heap uppercase even though it's declared with final because it's an array. If a variable is an array (and isn't declared in the parameters) and is declared with final is the convention to still name it all in uppercase?
• Benjamin Kuykendall: According to the Oracle style guide, SCREAMING_SNAKE_CASE is only to be used for class constants. All other variable names should be camelCase. This includes method parameters, final or not.
• Tunaki: @kidinme12 Look at Benjamin Kuykendall's comment above. By 'constants', I mean fields declared as static final.

Answer 2

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 <= end; i++) {
 if (heap[i] > heap[i/2]) {
 return false;
 }
 }
 return true;
}