The comparision comp.compare(items.get(r), items.get(l)) > 0
in shiftDown()
seems to be inverted.
Inverting it (and renaming variable max for clarity) the algorithm seems to work (as far as I've tested).
private void siftDown() {
int k = 0;
int l = 2*k+1;
while (l < items.size()) {
int min=l, r=l+1;
if (r < items.size()) { // there is a right child
if (comp.compare(items.get(r), items.get(l)) < 0) {
min = r;
}
}
if (comp.compare(items.get(k), items.get(min)) > 0) {
// switch
E temp = items.get(k);
items.set(k, items.get(min));
items.set(min, temp);
k = min;
l = 2*k+1;
} else {
break;
}
}
}
If I insert [20, 15, 11, 1, 29, 10, 7, 28, 3, 54, 40, 34, 58] I retrieve [1, 3, 7, 10, 11, 15, 20, 28, 29, 34, 40, 54, 58] which looks nice.
Hope it helps!