algorithm - 最小堆的摊销分析？

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)

谁能帮我解释一下？

Answer 1

根据您的问题和对评论的回复，我将假设一个二进制堆。

首先，插入的最坏情况是 O(log n)，移除最小项的最坏情况是 O(log n)。这是从堆的树结构得出的。也就是说，对于 n 项的堆，树中有 log(n) 层。

插入涉及(逻辑上)将项目添加为树中最右下角的节点，然后将其“冒泡”到所需的级别。如果新项小于根，则它必须一直冒泡到顶部——所有 log(n) 级别。因此，如果您将数字 10、9、8、7、6、5、4、3、2、1 插入到最小堆中，每次插入都会遇到最坏的情况。

最小元素的移除涉及用最后一项替换最低项(根)，然后将该项“筛选”到适当的位置。同样，这可能需要 log(n) 次操作。

那是最坏的情况。 平均情况大不相同。

请记住，在二叉堆中，一半的节点是叶节点——它们没有子节点。因此，如果您以随机顺序插入项目，一半时间您插入的项目将属于最低级别，并且没有“冒泡”可做。所以一半时间你的插入操作是 O(1)。在另一半中，那些 的一半属于第二层。等等。您实际对插入执行 log(n) 操作的唯一一次是当您插入的项目小于现有的根项目时。那么，很可能观察到的运行时行为是插入是 O(1)。事实上，如果将排序数组插入最小堆，就会出现这种情况。也就是说，如果您要按顺序插入值 1、2、3、4、5、6、7、8、9、10。

从最小堆中移除最小项时，您会从堆中取出最后一项并将其从顶部向下筛选。 “一半时间”规则再次发挥作用，但这次它对你不利。您从堆中取出的最后一项可能属于最低层。所以你必须一直筛选它，这需要 log(n) 操作。 一半时间您必须对所有 log(n) 操作执行操作。剩下的一半你需要做，除了其中一个，等等。事实上，你必须筛选的最少级别数将取决于树的深度。例如，如果您的堆有超过三个项目，那么您知道删除最小的项目将需要至少一次筛选操作，因为下一个最低的项目总是在树的第二层.

事实证明，在平均情况下，插入二叉堆所花费的时间远少于 O(log n) 时间。它可能更接近 O(1)。从二叉堆中移除更接近 O(log n) 的最坏情况。