在heapsort下限？

Question

众所周知,heapsort的最坏情况运行时为Ω(n lg n),但我很难理解为什么会这样.特别是,heapsort的第一步(制作最大堆)需要时间Θ(n).然后是n次删除.我理解为什么每个堆删除需要时间O(lg n); 重新平衡堆涉及一个向下泡沫的操作,它在堆的高度花费时间O(h),并且h = O(lg n).但是,我没有看到为什么第二步应该采用Ω(n lg n).似乎任何单个堆出列都不一定会导致节点移动到顶部以一直向下冒泡到树中.

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

Answer 1

所以我做了一些挖掘自己,看起来这个结果实际上是最近的!我能找到的第一个下限证据来自1992年,尽管heapsort本身是在1964年发明的.

正式的下限证据是由Schaffer和Sedgewick的"The Heaport分析"论文引起的.这是一个略微复述的证明版本,省略了一些技术细节.

首先,假设对于某些k,n = 2 ^k - 1,这保证了我们有一个完整的二进制堆.我稍后将展示如何单独处理此案例.因为我们有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个最大节点.那么这些节点的每个父节点也必须是k-2级的大节点.即使在最好的情况下,这意味着在^k-2级中必须至少有2个^k-3 + 1个大节点,这意味着在^k-3等级中至少有2个^k-4 + 1个大节点.总结所有这些节点,我们得到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级别,因此至少有2 ^k-2 - 2 ^{k- 3} = ^k-2级中的2 ^k-3个重节点.因此,需要执行的交换总数至少为(k-2)2 ^k-3.由于n = ^2k -1,k =Θ(lg n),因此该值根据需要为Θ(n lg n).