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.