sorting - 堆排序时间复杂度深入理解

Question

当我在大学学习数据结构类(class)时，我学到了以下公理:

1. 在最坏的情况下，向堆中插入一个新数字需要 O(logn)(取决于它作为叶子插入时在树中到达的高度)

2. 构建n 个节点的堆，使用n 个插入，从一个空堆开始，总计为O(n) 时间，使用摊销分析

3. 在最坏的情况下，移除最小值需要 O(logn) 时间(取决于新的顶部节点在与最后一个叶子交换后到达的最低点)

4. 将所有最小值一一移除，直到堆为空，耗时O(nlogn)时间复杂度

提示“堆排序”算法的步骤是:

• 将所有数组值添加到堆中:使用摊销分析技巧求和到 O(n) 时间复杂度
• 从堆中弹出最小值 n 次并将第 i 值放入数组的第 i 索引中: O(nlogn) 时间复杂度，因为摊销分析技巧在弹出最小值时不起作用

我的问题是:为什么摊销分析技巧在清空堆时不起作用，导致堆排序算法花费O(nlogn)时间而不是< strong>O(n) 次？

编辑/回答

当堆存储在数组中(而不是带有指针的动态树节点)时，我们可以自底向上构建堆，即从叶子开始向上到根，然后使用摊销分析我们可以得到O(n) 的总时间复杂度，而我们不能清空堆最小值的自下而上。

Answer 1

假设您只能通过比较两个对象来了解它们的相对排名，那么就无法在时间 O(n) 内从二叉堆中取出所有元素。如果你能做到这一点，那么你可以通过在时间 O(n) 内构建堆然后在时间 O(n) 内将所有内容出队来在时间 O(n) 内对列表进行排序。但是，排序下限表示比较排序为了正确，平均运行时间必须为 Ω(n log n)。换句话说，您不能太快地从堆中出列，否则您会打破排序障碍。

还有一个问题是为什么从二叉堆中取出 n 个元素需要时间 O(n log n) 而不是更快。展示起来有点棘手，但这是基本思想。考虑您在堆上进行的出列的前半部分。查看实际出列的值并考虑它们在堆中的位置。除了最下面一行的那些，其他所有出队的东西都必须一次一个交换地渗透到堆的顶部才能被删除。您可以证明堆中有足够的元素来保证仅此一项就需要时间 Ω(n log n)，因为这些节点中大约有一半将位于树的深处。这解释了为什么摊销论点不起作用——你不断地将深层节点拉到堆上，所以节点必须移动的总距离很大。将此与 heapify 操作进行比较，其中大多数节点移动的距离非常短。