二叉堆的摊销分析
amortized analysis on a binary heap
所以一个普通的二叉堆有一个操作 extract_min 这是 O(log(n)) 最坏的时间。假设 extract_min 的摊销成本为 O(1)。设 n 为堆的大小
所以我们执行了 n extract_min 个操作的序列，它最初包含 n 个元素。这是否意味着整个序列将在 O(n) 时间内处理，因为每个操作都是 O(1)？
让我们先解决这个问题：通过 extract_min 操作删除堆中的所有元素需要 O(N log N) 时间。
这是事实，所以当你问"Does constant amortized time extract_min imply linear time for removing all the elements?"时，你真正问的是"Can extract_min take constant amortized time even though it takes O(N log N) time to extract all the elements?"
这个问题的答案实际上取决于堆支持什么操作。
如果堆仅支持 add 和 extract_min 操作，那么每个 extract_min 没有失败（在恒定时间内）必须对应于前一个 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 操作，我们可以 not 声称 extract_min 需要摊销常数时间。
所以一个普通的二叉堆有一个操作 extract_min 这是 O(log(n)) 最坏的时间。假设 extract_min 的摊销成本为 O(1)。设 n 为堆的大小
所以我们执行了 n extract_min 个操作的序列，它最初包含 n 个元素。这是否意味着整个序列将在 O(n) 时间内处理，因为每个操作都是 O(1)？
让我们先解决这个问题：通过 extract_min 操作删除堆中的所有元素需要 O(N log N) 时间。
这是事实，所以当你问"Does constant amortized time extract_min imply linear time for removing all the elements?"时，你真正问的是"Can extract_min take constant amortized time even though it takes O(N log N) time to extract all the elements?"
这个问题的答案实际上取决于堆支持什么操作。
如果堆仅支持 add 和 extract_min 操作，那么每个 extract_min 没有失败（在恒定时间内）必须对应于前一个 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 操作，我们可以 not 声称 extract_min 需要摊销常数时间。