Потенциальная функция двоичного извлечения кучи max O (1)

Мне нужна помощь в определении потенциальной функции для максимальной кучи, так что извлечение max завершается за время амортизации . Я должен добавить, что у меня нет хорошего понимания потенциального метода. $O(1)$

Я знаю, что функция вставки должна «платить» больше, чтобы уменьшить стоимость извлечения, и это должно быть в отношении высоты кучи (если дает высоту куча должна быть вставка или ) $\lfloor \log(n) \rfloor$ $2\log(n)$ $\sum_{k=1}^n 2\log(k)$

data-structures runtime-analysis heaps amortized-analysis андрей
источник

Попробуйте следующее:

Вес элемента в куче - это его глубина в соответствующем двоичном дереве. Таким образом, элемент в корне имеет нулевой вес, два его ребенка имеют вес 1 и так далее. Вы определяете как потенциальную функцию $w_i$ $i$ $H$

Φ (ЧАС) знак равно \underset{я \in ЧАС}{Σ} 2 {вес}_{я},

$\Phi(H)=\sum_{i\in H}2 w_i.$

Давайте теперь проанализируем операции с кучей. Для вставки вы добавляете новый элемент, добавьте глубину не более . Это увеличивает потенциал, , и может быть сделано в времени. Затем вы «всплываете» новый элемент кучи, чтобы обеспечить свойство кучи. Это занимает времени и оставляет без изменений. Таким образом, затраты на вставку составляют $d$ $\log(n)$ $2d$ $O(1)$ $O(\log n)$ $\Phi(H)$ . $O(\log(n)+\Delta(\Phi(H)))=O(\log n)$

Теперь рассмотрим экстракт Мин . Вы вынимаете корень и заменяете его последним элементом в куче. Это уменьшает потенциал на , таким образом, вы можете позволить себе восстановить свойство кучи, и поэтому амортизированные затраты теперь составляют . $2\log(n)$ $O(1)$

Если у вас есть общий вопрос о потенциальной функции, вы должны поставить его как другой вопрос.

A.Schulz
источник

Я уверен, что вы правы, но я не понял вставку. Почему

без изменений? Извините , если ответ очевиден , но не могли бы Вы расширить

? Я не могу понять, почему у вас там отрицательное число

Δ (Φ (H)))

$\Delta(\Phi(H)))$

Δ

$\Delta$

Андрей

относится к разности потенциалов - до и после вставки. В случае вставки не более

. Когда вы меняете два элемента в куче (всплывающее или всплывающее), один вес получает +1, а другой получает -1 изменение, поэтому потенциал (сумма всех весов) остается неизменным.

Δ (Φ (H))

$\Delta(\Phi(H))$

2 \log (n)

$2\log(n)$

А.Шульц

Как ремонт O (1)? Какая польза от потенциальной функции при восстановлении кучи? Не могли бы вы уточнить

Сохаиб

O (\log n)

$O(\log n)$

O (1)

$O(1)$

@ A.Schulz Таким образом, это, по сути, означает, что, учитывая, что операция извлечения выполняется n раз, так как каждый раз потенциальная функция уменьшается на 2 лога (может увеличиваться или не увеличиваться одинаково при восстановлении). Общая сложность такой вещи будет постоянной, поскольку в конечном итоге в дереве не будет ни одного узла. Я прав?

Сохаиб

Потенциальная функция двоичного извлечения кучи max O (1)

Ответы: