Таким образом, обычная двоичная куча имеет операцию extract_min, которая имеет наихудшее время O(log(n)) . Предположим, что амортизированная стоимость extract_min равна O(1). Пусть n будет размером кучи
Итак, последовательность, в которой мы выполнили n операций extract_min и изначально содержала n элементов. Означает ли это, что вся последовательность будет обработана за время O(n), поскольку каждая операция выполняется за O(1)?
Давайте сначала разберемся с этим: удаление ВСЕХ элементов в куче с помощью extract_min операций занимает O(N log N) время.
Это факт, поэтому, когда вы спрашиваете: «Подразумевает ли постоянное амортизированное время extract_min линейное время для удаления всех элементов?», на самом деле вы спрашиваете: «Может ли extract_min принимать постоянное амортизированное время, даже если для этого требуется O(N log N) пора извлечь все элементы?"
Ответ на этот вопрос на самом деле зависит от того, какие операции поддерживает куча.
Если куча поддерживает только операции 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 операциям, и мы не можем не утверждать, что extract_min занимает амортизированное постоянное время.
