Dutton presents a further HEAPSORT variant called
WEAK-HEAPSORT which also contains a new data structure for
priority queues. The sorting algorithm and the underlying
data structure ara analyzed showing that WEAK-HEAPSORT is
the best HEAPSORT variant and that it has a lot of nice
properties. It is shown that the worst case number of
comparisons is smaller than nlog n + 0.1 n and weak heaps
can be generated with n-1 comparisons. A double-ended
priority queue based on weak-heaps can be generated
in 1.5 n -1 comparisons. Moreover, examples for the
worst and the best case of WEAK-HEAPSORT are presented,
the number of Weak-Heaps on {1...n} is determined and
experiments on the average case are reported.