当我在大学学习数据结构课程时，我学到了以下公理：
-
在最坏的情况下将新数字插入堆需要 O(logn) （取决于作为叶插入时它到达树中的高度）
-
使用 n 节点构建一堆 n 节点，从空堆开始，使用摊销分析求和为 O(n) 时间
-
在最坏情况下删除最小值需要 O(logn) 时间（取决于新顶节点在与最后一个叶子交换后达到的低点）
-
逐个删除所有最小值，直到堆为空，需要 O(nlogn) 时间复杂度
Reminder: "heapsort"算法的步骤是：
-
将所有数组值添加到堆中：使用摊销分析技巧求和为 O(n) 时间复杂度
-
弹出堆中的最小值 n 次并将 i -th值放在数组的 i -th索引中：O（nlogn）时间复杂度，因为当弹出最小值时，摊销分析技巧不起作用
My question is ：为什么在清空堆时，分摊分析技巧不起作用，导致堆排序算法占用 O(nlogn) 时间而不是 O(n) 时间？
1 回答
假设您只允许通过比较它们来了解两个对象的相对排名，那么就无法在时间O（n）中将所有元素从二进制堆中出列 . 如果你能做到这一点，那么你可以通过在时间O（n）中构建一个堆，然后在时间O（n）中出列所有内容，在时间O（n）中对列表进行排序 . 但是，排序下限表示比较排序，为了正确，平均必须具有Ω（n log n）的运行时间 . 换句话说，你不能太快从堆中出队，或者你打破了排序障碍 .
还有一个问题是，为什么从二进制堆中出列n个元素需要时间O（n log n）而不是更快 . 这显示有点棘手，但这是基本的想法 . 考虑一下你在堆上出列的前半部分 . 查看实际出列的值，并考虑它们在堆中的位置 . 排除底行的那些，所有出列的其他东西必须一次渗透到堆顶部一次，以便被移除 . 您可以显示堆中有足够的元素来保证单独使用时间Ω（n log n），因为这些节点中大约有一半将位于树的深处 . 这解释了为什么摊销的论证不起作用 - 你不断地将深层节点拉到堆上，因此节点必须行进的总距离很大 . 将其与heapify操作进行比较，其中大多数节点行进的距离非常短 .