algorithm - 堆排序的下界？

Question

众所周知，堆排序的最坏运行时间是 Ω(n lg n)，但我很难理解这是为什么。特别地，heapsort 的第一步(创建最大堆)需要时间 Θ(n)。然后是 n 堆删除。我明白为什么每次堆删除都需要时间 O(lg n);重新平衡堆涉及冒泡操作，该操作在堆的高度上需要时间 O(h)，并且 h = O(lg n)。但是，我不明白为什么第二步应该采用 Ω(n lg n)。似乎任何单独的堆出队都不一定会导致节点移动到顶部以一直冒泡到树下。

我的问题是 - 有没有人知道堆排序最佳情况行为的良好下限证明？

Answer 1

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

正式的下界证明来自 Schaffer 和 Sedgewick 的“堆排序分析”论文。这是省略了一些技术细节的证明的略微释义版本。

首先，让我们假设 n = 2^k - 1 对于某些 k，这保证我们有一个完整的二叉堆。稍后我将单独展示如何处理这种情况。因为我们有 2^k - 1 个元素，heapsort 的第一遍将在 Θ(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 层的大节点。即使在最好的情况下，这也意味着至少有 2^k-3 + 1 个大节点k - 2，这意味着至少有 2^k-4 + 1 个大节点在第 k - 3 层，等等。对所有这些节点求和，我们得到有 2 ^k-2 + 2^k-3 + 2^k-4 + ... + 2⁰ + k大节点。但是这个值严格大于 2^k-1，这与我们在这里只使用 2^k-1 个节点的事实相矛盾。

好的...我们现在知道底层最多有2^k-2个大节点。这意味着在前 k-2 层中必须至少有 2^k-2 个大节点。我们现在问——所有这些节点上从该节点到根的距离的总和是多少？好吧，如果我们有 2^k-2 个节点位于一个完整堆的某处，那么它们中最多有 2^k-3 个可以在前 k - 3 层中，因此在第 k - 2 层至少有 2^k-2 - 2^k-3 = 2^k-3 个重节点。因此，需要执行的交换总数至少为 (k - 2) 2^k-3。由于n = 2^k-1，k = Θ(lg n)，所以这个值按要求为Θ(n lg n)。