A sorting algorithm developed by Williams and Floyd in 1964 and
employing the ideas of tree selection. It is more
efficient for larger numbers of records but on average is inferior to
quicksort. However, the worst possible
distribution of keys does not cause the efficiency of heap-sort to deteriorate
too much. The worst case for quicksort can then be worse. Some of the ideas of
heapsort are relevant to priority queue applications.