Heapsort上的下限？

Question

众所周知，Hepsort最糟糕的运行时间是ω（n Lg n），但是我很难看到为什么这是ω（n lg n）。特别是，hepsort的第一步（制作最大值）需要时间θ（n）。然后是n堆删除。我了解为什么每个堆删除需要时间O（lg n）；重新平衡堆涉及一个气泡的操作，该操作需要时间O（H）在堆的高度上，H = O（lg n）。但是，我看不到的是为什么第二步应采取ω（n lg n）。似乎任何单独的堆dequeue都不一定会导致节点移至顶部，从而一直沿着树下的气泡。

我的问题是 - 有人知道Heapsort的最佳案例行为是否有良好的下限证明？

Answer 1

因此，我做了一些挖掘自己，看起来这个结果实际上是相当新近的！我能找到的第一个较低的证据是从1992年开始，尽管Heperort本身是在1964年发明的。

正式的下限证明是由于Schaffer和Sedgewick的“ Heapsort分析”纸。这是省略一些技术细节的证明版本的略微释义。

首先，让我们假设n = 2^k -1对于某些K，可以保证我们有一个完整的二进制堆。我将稍后展示如何分别处理此情况。因为我们有2个^k -1个元素，Heapsort的第一个通行证将在θ（n）中建立高度k。现在，考虑从该堆的上半部分的上半部分，它去除了2^K-1 堆的节点。第一个关键观察是，如果您占据起始堆，然后在这里标记所有最终被脱水的节点，它们会形成堆的子树（即，脱水的每个节点都有一个父母也会被脱水的父母）。您可以看到这一点，因为如果不是这种情况，那么如果节点本身被脱水，则会有一些节点（较大的）父母不会被脱水，这意味着值不在顺序。

现在，考虑如何在整个堆之间分布这棵树的节点。如果您标记堆0、1、2，...，k -1的级别，则将在0、1、2，...，k -2中有一些这些节点（即，即，除了树的底层以外的所有内容）。为了使这些节点从堆中脱水，然后必须将它们换成根，并且一次只会被换成一个级别。这意味着，降低heapsort的运行时的一种方法是计算将所有这些值提高到根的所需掉期数量。实际上，这正是我们要做的。

我们需要回答的第一个问题是 - 最大的2个^K-1 节点不在堆的底部？我们可以证明这不超过2^K-2 矛盾。假设至少有2个^K-2 + 1个最大节点中的1个。那么这些节点的每个父母也必须是K -2级的大节点。即使在最好的情况下，这意味着至少必须有2个^K-3 +级别K -2中的1个大节点，这意味着至少有2个^K-4 +级别K -3等中的1个大节点等。总结所有这些节点，我们知道有2个^K-2 + 2^K-3 + 2^K-4 + ... + 2⁰ + k大节点。但是这个价值严格大于2^K-1, ，与我们仅合作2的事实相矛盾^K-1 节点在这里。

好吧...我们现在知道最多有2^K-2 底层中的大节点。这意味着至少必须有2个^K-2 第一个K-2层中的大节点。我们现在问 - 从该节点到根的距离，所有这些节点的总和是多少？好吧，如果我们有2个^K-2 节点位于完整堆中的某个地方，然后最多2^K-3 其中可以在第一个K -3级别中，因此至少有2个^K-2 - 2^K-3 = 2^K-3 级别K -2中的重节点。因此，至少需要执行的互换总数至少为（k -2）2^K-3. 。由于n = 2^k-1，k =θ（lg n），因此此值为θ（n lg n）。

Answer 2

简单的观察答案是：堆中的项目是：

1
2
4
8
...
2^[log(n/4)]
and last level has between (1..2^[log(n/2)]) ==> (1,[n/2]) item, (by [] I mean Ceiling not roof)

例如，如果您有7个项目：

1
2
4

如果您有8个项目：

1
2
4
1

有2棵不同的堆树，首先至少是堆的N/4-1个项目，或者至少没有 n/4 - 1 上一个之前的项目，在第一种情况下，它需要 O((n/4 - 1) * log(n/2)) 要从堆中删除最后一个级别的项目，在第二种情况下，它需要 O((n/4 - 1) * log(n/4)) 从最后一个级别删除项目。因此，在两种情况下，仅适用于N/4-1个项目，因此需要ω（n log（n）），因此它是一个下限（很容易说出它是紧密的下限）。

Answer 3

这是使用CLRS术语的解决方案：
我们从一个最大矿井开始，这是一棵完整的二进制树 n 元素。
我们可以说，有一个完整的二元 n/2 叶和 n/2 内部节点。
n/2 迭代 HEAP-SORT 删除最大的 n/2 堆的元素。
让 S 成为最大的集合 n/2 元素。
最多可以 n/4 来自 S 在叶子里，因为必须还有其他 n/4 它们在内部节点中。
让 L 是这些 n/4 最大的元素 S 在叶子里。
所以如果有 n/4 来自 S 在0级（叶级），至少必须有 n/8 他们在1级。
让 P 是这些 n/8 来自 S 在1级。
n/2 堆积的迭代可能会给 L 缩短根部，然后从堆中脱出，但是 P 必须在将它们从堆中取出之前一直延伸到根。
所以至少有 (n/8)(lgn-1) 操作，这使我们的运行时间为ω（NLGN）。
现在，对于没有所有叶子在0级的最大叶子的情况下。
让 k 在0级处是其叶子的数量。
后 k 堆积的迭代，我们留下了一个最大壁，是一棵完整的二进制树 lgn-1.
我们可以以相同的方式继续我们的证明。
现在对于少于 n/4 叶子 S.
让 k 是来自 S 在0级的叶子中。
如果 k <= n/8 那么至少必须有 n/8 来自 S 在1级。
这是因为总共可以 n/4 高于1级的元素。
我们以相同的方式继续证明。
如果 k>n/8 那么至少必须有 n/16 来自 S 在1级。
我们以相同的方式继续证明。
我们得出结论，堆组的运行时间为ω（NLGN）。