堆排序

优先队列可以用于花费 时间的排序，基于该想法的算法叫作堆排序（heapsort），该算法的运行时间很优秀，然后，在实践中它却慢于使用 Sedgewick 增量序列的希尔排序。

该算法的主要问题在于它使用了一个附加的数组。因此，存储需求增加一倍。在某些实例中这可能是个问题。注意，将第二个数组拷贝回第一个数组的额外时间消耗只是 ，这不可能显著影响运行时间。这个问题是空间的问题。

避免使用第二个数组的聪明做法是利用这样的事实：在每次 DeleteMin 之后，堆缩小了 1。因此，位于堆中最后的单元可以用来存放刚刚删去的元素。

经验指出，堆排序是一个非常稳定的算法：它平均使用的比较只比最坏情形界指出的略少。然而直到最近，还没有人能够指出堆排序平均运行时间的非平凡界。似乎问题在于连续的 DeleteMax 操作破坏了堆的随机性，使得概率论证非常复杂。

定理：堆 N 个互异项的随机排列进行堆排序，所用的平均比较次数为 ——。