最小堆的摊销分析？

Question

如果我们在空的最小堆上进行n个任意插入和删除操作（给定删除位置在最小堆中），为什么插入的平摊分析是O(1)，而删除是O(log n)？

a) insert O(log n), delete O(1)

b) insert O(log n), delete O(log n) 

c) insert O(1), delete O(1)

d) insert O(1), delete O(log n)

有人能为我澄清这个问题吗？（涉及IT技术）

- user4672610

---

有些人怀疑最小堆的插入时间复杂度应该是O(lg n)，因为每次插入都需要进行“重构”或者叫“上浮操作”，无论你如何称呼它，其本身的时间复杂度就是O(lg n)。参考链接：http://en.wikipedia.org/wiki/Binary_heap#Insert - Jason Hu

可能是斐波那契堆，它具有O(1)的插入时间复杂度。 - David Eisenstat

除非告诉我们你使用的是什么类型的堆，否则你的问题没有有意义的答案。它是二叉堆吗？ - Jim Mischel

@JimMischel，我认为我们必须从选择中猜测。这在我的笔记中没有提到... - user4672610

@DavidEisenstat，这在我的笔记中没有提到... - user4672610

Answer 1

根据您的问题和对评论的回复，我假设您在谈论二叉堆。

首先，插入的最坏情况是O(log n)，删除最小项目的最坏情况也是O(log n)。这是由于堆的树形结构造成的。也就是说，对于n个元素的堆，树中有log(n)层。

插入操作（逻辑上）涉及将项目添加为树中最低的右节点，然后将其“冒泡”到所需的层级。如果新项目小于根，则必须冒泡到顶部-所有log(n)层。因此，如果您向min-heap中插入数字10, 9, 8, 7, 6, 5, 4, 3, 2, 1，那么每次插入都会达到最坏的情况。

删除最小元素涉及用最后一个元素替换最低的元素（根），然后将该项“筛选”到其正确位置。同样，这可能需要进行多达log(n)次操作。

那是最坏的情况。平均情况则完全不同。

请记住，在二叉堆中，一半的节点是叶子节点-它们没有孩子。因此，如果您按随机顺序插入项目，有一半的时间您要插入的项目将属于最低层，这时就不需要“冒泡”操作。因此，有一半的时间插入操作是O(1)。对于另一半，有一半的时间它们将属于上面第二层。等等。只有在要插入的项目小于现有根项目时才实际执行log(n)次操作。因此，观察到的运行时行为可能是插入为O(1)。实际上，如果您按顺序向min-heap中插入排序数组，那么这将是行为。也就是说，如果您按顺序插入值为1、2、3、4、5、6、7、8、9、10的值。

从min-heap中删除最小项时，您需要从堆中获取最后一个项，并从顶部开始筛选。再次使用“一半的时间”规则，但这次它与您作对。您从堆中取出的最后一个项可能属于最低层。因此，您需要将其全部筛选回去，这需要进行log(n)次操作。有一半的剩余时间，您需要做所有除一项之外的操作，依此类推。实际上，您必须筛选的最小级别取决于树的深度。例如，如果堆具有三个以上的项，则您知道删除最小项将需要至少一个筛选操作，因为下一个最低项始终在树的第二层。

事实证明，平均情况下插入二叉堆所需的时间远远小于O(log n)。很可能更接近于O(1)。而从二叉堆中删除则更接近于最坏情况的O(log n)。

- Jim Mischel

---

@user4249446：我觉得这个问题和提供的解决方案相当令人困惑。话虽如此，解决方案中没有任何与我在答案中说的相矛盾的地方。 - Jim Mischel

你说插入的时间复杂度是O(1)，删除的时间复杂度是O(log n)，但链接上说插入的时间复杂度是O(log n)，删除的时间复杂度是O(1)摊销成本？我错了吗？ - user4249446

@user4249446：不是说插入是O(1)，删除是O(log n)。我特别说明了我的分析仅限于二叉堆。如果你使用其他类型的堆（配对堆、斐波那契堆等），那么行为将会有所不同。我给出的答案是基于你提出的问题，而不是你发布链接的作业问题。 - Jim Mischel

谢谢，+1。我的问题是为什么发布的作业没有关于堆的定义，但是说插入O(log n)，删除O(1)摊销成本。谢谢。 - user4249446

再次感谢您，我在这里提出了新的挑战：http://stackoverflow.com/questions/29288775/amortized-analysis-on-heap-and-big-challenge-in-my-life - user4249446