众所周知，heapsort最坏的运行时是Ω（n lgn），但我很难理解这是为什么。特别是，heapsort（生成最大堆）的第一步需要时间_（n）。接下来是n个堆删除。我理解为什么每次删除堆都需要时间o（lg n）；重新平衡堆需要一个气泡下降操作，该操作需要时间o（h）在堆的高度，以及h=o（lgn）。但是，我不明白为什么第二步应该是Ω（n lgn）。看起来，任何单独的堆出列都不一定会导致节点移动到树的顶部，沿着树一直冒泡。
我的问题是-有谁知道heapsort的最佳案例行为的一个好的下限证明吗？
最佳答案
所以我做了一些自我挖掘，看起来这个结果实际上是相当新的！我能找到的第一个下限证明是1992年，尽管heapsort本身是1964年发明的。
形式下界证明是由schaffer和sedgewick的《heapsort分析》一文提出的。这里有一个略带释义的证明版本，省略了一些技术细节。
首先，假设对于某些k，n=2k-1，这保证了我们有一个完整的二进制堆。稍后我将分别介绍如何处理这个案子。因为我们有2k-1元素，heapsort的第一次传递将在_（n）中建立一个高度为k的堆。现在，考虑从这个堆中删除2k-1节点的dequeues的前半部分。第一个关键的观察结果是，如果取开始堆，然后在这里标记所有实际结束排队的节点，它们将形成堆的子树（即，每个退出队列的节点都有一个父节点也将退出队列）。您可以看到这一点，因为如果不是这样的话，那么会有一个节点的（较大的）父节点没有进入队列，尽管该节点本身已经退出队列，这意味着这些值是无序的。
现在，考虑一下这个树的节点是如何分布在堆中的。如果标记堆0、1、2、…、k-1的级别，那么在0、1、2、…、k-2级别（即除树的底部级别之外的所有级别）中将有一些节点。为了让这些节点从堆中退出队列，必须将它们交换到根节点，并且它们一次只能交换一个级别。这意味着降低heapsort运行时的一种方法是计算将所有这些值带到根目录所需的交换次数。事实上，这正是我们要做的。
我们需要回答的第一个问题是-有多少最大的2K-1节点不在堆的底层？我们可以用矛盾的方法证明它不大于2k-2。假设堆的底层至少有2k-2+1个最大的节点。那么这些节点的每个父节点也必须是级别K-2中的大节点。即使在最好的情况下，这意味着在k-2级必须至少有2k-3+1个大节点，这意味着在k-3级将至少有2k-4+1个大节点，等等。总结所有这些节点，我们得到有2k-2+2k-3+2k-4+…+20+k个大节点。但是这个值严格地大于2k-1，这与我们只处理2k-1节点的事实相矛盾。
可以。。。我们现在知道在底层最多有2K-2个大节点。这意味着在第一个k-2层中必须至少有2k-2个大节点。我们现在要问-在所有这些节点上，从该节点到根节点的距离之和是多少？好吧，如果我们在一个完整的堆中的某个地方有2K-2节点，那么它们中最多有2K-3可以在第一个K-3级别，因此在第K-2级别中至少有2K-2-2K-3=2K-3重节点。因此，需要执行的交换的总数至少为（k-2）2k-3。由于n=2k-1，k=_（lg n），因此该值为所需的_（n lg n）。
关于algorithm - 堆排序的下限？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/4589988/