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

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.

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