data-structures - 二叉堆的摊销分析

Question

所以一个常规的二叉堆有一个操作 extract_min 是 O(log(n)) 最坏的时间。假设 extract_min 的摊销成本为 O(1)。设 n 为堆的大小

因此，我们执行了 n 个 extract_min 操作的序列，它最初包含 n 个元素。这是否意味着整个序列将在 O(n) 时间内处理，因为每个操作都是 O(1)？

Answer 1

让我们先解决这个问题：通过extract_min操作删除堆中的所有元素需要O(N log N)时间。

这是事实，所以当您问“恒定摊销时间是否extract_min意味着删除所有元素的线性时间？”时，您真正要问的是“extract_min即使提取需要O(N log N)时间，也可以花费恒定摊销时间所有元素？”

这个问题的答案实际上取决于堆支持的操作。

如果堆只支持addandextract_min操作，那么每一个extract_min不失败（在恒定时间内）必须对应于一个 previous add。然后我们可以说这add需要分期O(log N)时间，并且extract_min需要分期O(1)时间，因为我们可以将其所有非常量成本分配给先前的add.

但是，如果堆支持O(N)时间make_heap操作（摊销或不摊销），则可以执行N extract_min操作而无需执行任何其他加起来O(N log N)时间的操作。然后必须将整个O(N log N)成本分配给N 个 extract_min操作，我们不能声称这extract_min需要摊销的常数时间。