Theoretically a very efficient sort. Bounded in O(n log n) for both comparisons and exchanges. Fairly complex to understand though. A generalization of selection sort.
I suspect it is taught only because it is complex to understand and makes nice exam subjects. Otherwise, it is less efficient than dichotomic insertion in general, twice longer than quicksort or shell sort in general, and is never optimal for any kind of distribution.
class HeapSort extends AlgoTri {
HeapSort (int t, VueTris v) { super("HeapSort", t, v); }
boolean isLeaf(int t, int pos) {
return (pos >= t/2)
&& (pos < t) && t > 0;
}
int leftchild(int pos) {return 2*pos+1;}
int rightchild(int pos) {return 2*pos;}
void siftdown (int t, int pos) {
while (!isLeaf(t, pos)) {
int j = leftchild(pos);
int k = rightchild(pos);
int maxchildindex;
if (compare(k,j) < 0) maxchildindex=j;
else maxchildindex=k;
if (compare(pos, maxchildindex) >= 0) return;
exchange(pos, maxchildindex);
pos = maxchildindex;
}
}
public void sort () {
for (int i = size/2-1; i>=0; i--)
siftdown(size-1, i);
for (int i=size-1; i>1; i--) {
exchange(0,i);
siftdown (i-1, 0);
}
}
};