heapifyDown in heapsort

Question

This is for heapsort and am wondering about the heapifyDown method. Here it is for review. I included relevant helper methods.

The heap is stored in array starting at index 1.

/*swaps node at i with biggest child if larger*/
private void heapifyDown(final int i) {
    while(!isLeaf(i)) {
        //find biggest child
        int biggestChldIndx;
        if(getRgtChldIndx(i) <= end) {//check if node has right child
            if(heap[getLftChldIndx(i)] > heap[getRgtChldIndx(i)]) {
                biggestChldIndx = getLftChldIndx(i);
            } else {
                biggestChldIndx = getRgtChldIndx(i);
            }
        } else {//only has left child so use it
            biggestChldIndx = getLftChldIndx(i);
        }
        //check if child is larger than parent
        if(heap[i] < heap[biggestChldIndx]) {
            //if it is, then swap
            swap(i, biggestChldIndx);
            i = biggestChldIndx;
        } else {
            break;
        }
    }
}  

private boolean isLeaf(final int position) {
    return (2 * position > end);
}

private int getLftChldIndx(final int i) {
    return (i * 2);
}

private int getRgtChldIndx(final int i) {
    return (i * 2 + 1);
}

private final int[] heap;
private int end;//last used element

Answer 1

        int biggestChldIndx;
        if(getRgtChldIndx(i) <= end) {//check if node has right child
            if(heap[getLftChldIndx(i)] > heap[getRgtChldIndx(i)]) {
                biggestChldIndx = getLftChldIndx(i);
            } else {
                biggestChldIndx = getRgtChldIndx(i);
            }
        } else {//only has left child so use it
            biggestChldIndx = getLftChldIndx(i);
        }

You can simplify this somewhat.

        int biggerChildIndex = getLftChldIndx(i);
        int rightChildIndex = getRgtChildIndx(i);
        if (rightChildIndex <= end && heap[biggerChildIndex] <= heap[rightChildIndex]) {
            biggerChldIndx = rightChildIndex;
        }

The compiler would probably do most of that. The basic point is that there are only two possible values for biggerChildIndex. Since we need to fetch both values to pick the right one, we might as well assign one of them optimistically. Then we only have to check for the one path where it would be the other value.

I renamed it to biggerChildIndex because when you have two things, one is bigger than the other. Biggest implies that there are at least three. If interested, look up the difference between comparatives (e.g. bigger) and superlatives (e.g. biggest). A rather pedantic difference, but one that I happen to know.

I also prefer not to elide out letters. The minor savings in typing are outweighed by the cognitive increase in reading in my opinion. Since most code is read more than it is written, it makes more sense to optimize for reading.

You also might want to consider this pattern:

        for (int childIndex = getBiggerChildIndex(i); childIndex <= end && heap[i] < heap[childIndex]; childIndex = getBiggerChildIndex(i)) {
            swap(i, childIndex);
            i = childIndex;
        }

Some people prefer to iterate (which is what is happening here) with for loops rather than while loops. In this case, it simplifies the logic somewhat by allowing us to combine the two iteration checks. Previously you had to use a break because the second check was separated.

What you really want to know is that the child is inside the heap, not that i doesn't point to a leaf. The other logic works because when i is a leaf, there is no child (and therefore the loop has to stop iterating).

An argument against this is that it adds a method call to each iteration of the loop. Of course, the method might be inlined. As I suspect that the calls to getLftChldIndx and getRgtChldIndx are. Note that your original made at least two calls to those methods and possibly four on every iteration plus a call to isLeaf. This version makes exactly three method calls, the same as the minimum in the original version.

Possible implementation:

    int getBiggerChildIndex(final int parentIndex) {
        int leftChildIndex = getLftChldIndx(parentIndex);
        int rightChildIndex = getRgtChildIndx(parentIndex);
        if (rightChildIndex <= end && heap[rightChildIndex] >= heap[leftChildIndex]) {
            return rightChildIndex;
        }

        return leftChildIndex;
    }

It's possible to write this with the ternary operator as well, but the condition is long enough that I think the if is worth it for readability.

This is also slightly more readable in that it doesn't guess which one is bigger so as to save an unnecessary variable assignment. It returns instead.

Extraneous comment

            //if it is, then swap

Considering that this appears in an if statement and the next statement is swap, this is unnecessary.

Note that I actually removed all the comments. I believe that my code structure makes them obvious enough to be unnecessary. It's more borderline on the other two though.