所以我做了一些自我挖掘，看来这个结果实际上是最近的！我能找到的第一个下界证明是从1992年开始的，尽管heapsort本身是在1964年发明的。

正式的下界证明是基于Schaffer和Sedgewick的“ The Heapsort分析”论文。这是略微释义的版本，省略了一些技术细节。

首先，假设对于某些k，n = 2 k -1，这保证了我们有完整的二进制堆。稍后我将展示如何单独处理这种情况。因为我们有2 k
-1个元素，所以堆排序的第一遍将在Θ（n）中建立一个高度为k的堆。现在，请考虑此堆中出队的前半部分，这将删除2
k-1堆中的节点。第一个关键的观察结果是，如果您使用起始堆，然后在此处标记实际上最终出队的所有节点，它们将构成堆的子树（即，每个被出队的节点都有一个父节点也被出队）。您可以看到这是因为，如果不是这种情况，那么即使某个节点本身已经出队，也可能会有某个节点的（较大）父节点没有出队，这意味着值是乱序的。

现在，考虑该树的节点如何在整个堆中分布。如果您将堆的级别标记为0、1、2，…，k-1，那么在级别0、1、2，…，k-2中将有一定数量的这些节点（即，除了树的底层以外的所有内容）。为了使这些节点从堆中出队，必须将它们交换到根，并且一次只能交换一个级别。这意味着降低堆排序运行时间的一种方法是计算使所有这些值都达到根所必需的交换次数。实际上，这正是我们要做的。

我们需要回答的第一个问题是-最大的2 k-1个节点中有多少个不在堆的最底层？我们可以证明，这不大于2 k-2。假设堆最低层中至少有2 k-2
+1个最大节点。然后，这些节点的每个父节点也必须是k-2级的大节点。即使在最佳情况下，这也意味着k-2级必须至少有2 k-3 +
1个大节点。在k-3级中至少会有2 k-4 +1个大节点，依此类推。总结所有这些节点，我们得出有2 k-2 + 2 k-3 + 2 k-4 + …
+ 20 + k个大节点。但是此值严格大于2 k-1，这与我们在这里仅使用2 k-1个节点的事实相矛盾。

好的…我们现在知道在底层最多有2 k-2个大节点。这意味着在前k-2层中必须至少有2 k-2个大节点。现在我们问-
在所有这些节点上，从该节点到根的距离的总和是多少？那么，如果我们有2 K-2节点的地方放置在一个完整的堆，然后最多2 K-3人可在第一个K -
3个级别，因此至少有2 K-2 - 2 K-在级别k-2中3 = 2 k-3个重节点。因此，需要执行的交换总数至少为（k-2）2 k-3。由于n = 2
k-1，k =Θ（lg n），因此根据需要该值为Θ（nlg n）。