最小堆上插入/删除的摊余成本

Question

我最近遇到一个面试问题。没有给出任何额外的信息（也许应该使用默认实现......）

在空的最小堆上（删除元素的位置已知）上的 n 个任意序列的插入和删除操作的摊销成本为：

A) 插入 O(1)，删除 O(log n)

B) 插入 O(log n)，删除 O(1)

选项（B）正确。

看到答题纸我很惊讶。我知道这很棘手，也许是空堆，也许知道要删除的元素的位置，...我不知道为什么 (A) 是假的？为什么（B）是正确的？

Answer 1

将摊余成本分配给数据结构上的操作时，需要确保对于执行的任何操作序列，摊余成本总和始终至少与这些操作的实际成本总和一样大。

\n

因此，我们采用选项 1，它将 O(1) 的摊余成本分配给插入，将 O(log n) 的摊余成本分配给删除。我们要问的问题如下：对于空二进制堆上的任何操作序列，这些操作的实际成本是否真的以这些操作的摊余成本为上限？在这种情况下，答案是否定的。想象一下，您在堆中执行了一个纯粹由n次插入组成的序列。如果每个元素都必须一直冒泡到堆顶部，则执行这些操作的实际成本可能是 \xce\x98(n log n)。然而，使用这种会计方案，这些操作的摊余成本将为 O(n)，因为我们进行了 n 次操作，并假设每一次操作都花费 O(1) 时间。因此，这种摊销会计方案不起作用，因为它会让我们低估我们正在做的工作。

\n

另一方面，让我们看看选项 2，其中我们指定 O(log n) 作为我们的摊销插入成本，O(1) 作为我们的摊销删除成本。现在，我们能否找到包含 n 个操作的序列，其中这些操作的实际成本超过摊余成本？在这种情况下，答案是否定的。这是了解这一点的一种方法。我们将插入的摊余成本设置为 O(log n)，这与其实际成本相匹配，因此我们最终低估总成本的唯一方法是删除的摊销成本 (O(1) ），这低于删除的真实成本。然而，这在这里不是问题。为了能够执行删除操作，我们必须事先插入要删除的元素。插入和删除的组合实际成本为 O(log n) + O(log n) = O(log n)，插入和删除的组合摊余成本为 O(log n) + O(1 ) = O(log n)。因此，从这个意义上说，假装删除速度更快并不会改变我们的总体成本。

\n

要了解为什么第二种方法有效而第一种方法无效，一个很好的直观方法是思考摊销分析是什么。摊销背后的直觉是对早期操作​​收取更高的费用，以便未来的操作看起来花费更少的时间。在第二种会计方案的情况下，这正是我们正在做的：我们将从二进制堆中删除元素的成本转移回首先将该元素插入到堆中的成本。这样，由于我们只是将工作向后转移，摊余成本的总和不可能低于实际成本的总和。另一方面，在第一种情况下，我们正在向前推进工作通过删除插入来支付插入的费用，从而及时但这是一个问题，因为如果我们进行了一堆插入，然后从不进行相应的删除，我们就会将工作转移到不存在的操作上。

\n