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 heapsort 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.