Ekstrakt sterty binarnej funkcji potencjalnej max O (1)

Potrzebuję pomocy w określeniu funkcji potencjalnej dla stosu maksymalnego, aby wyciąg maksymalny został zakończony w czasie zamortyzowanym . Powinienem dodać, że nie rozumiem potencjalnie tej metody. $O(1)$

Wiem, że funkcja wstawiania powinna „płacić” więcej, aby zmniejszyć koszt wydobycia, i musi to dotyczyć wysokości stosu (jeśli podaje wysokość stosu, jeśli wstaw lub ) $\lfloor \log(n) \rfloor$ $2\log(n)$ $\sum_{k=1}^n 2\log(k)$

— Andrei
źródło

Spróbuj wykonać następujące czynności:

Masę elementu w stosie ma głębokość w odpowiednim drzewa binarnego. Tak więc element w korzeniu ma wagę zero, jego dwoje dzieci ma wagę 1 i tak dalej. Zdefiniujesz jako funkcję potencjalną $w_i$ $i$ $H$

Φ (H) = \sum_{i \in H} 2 w_{i} .

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

Przeanalizujmy teraz operacje sterty. Do wstawienia dodajesz nowy element, dodając głębokość co najwyżej . Zwiększa to możliwość przez i mogą być wykonane w czas. Następnie „powiększasz” nowy element sterty, aby zapewnić właściwość sterty. Zajmuje to czas i pozostawia bez zmian. Zatem koszty wstawienia wynoszą $d$ $\log(n)$ $2d$ $O(1)$ $O(\log n)$ $\Phi(H)$ . $O(\log(n)+\Delta(\Phi(H)))=O(\log n)$

Teraz rozważ ekstraktMin . Wyjmujesz korzeń i zastępujesz go ostatnim elementem w stercie. Zmniejsza to potencjał o , dlatego możesz sobie pozwolić na naprawę właściwości hałdy, a zatem zamortyzowane koszty wynoszą teraz . $2\log(n)$ $O(1)$

Jeśli masz ogólne pytanie dotyczące potencjalnej funkcji, powinieneś zadać to jako inne pytanie.

— A.Schulz
źródło

Δ (Φ (H)))

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

Δ

$\Delta$

Δ (Φ (H))

$\Delta(\Phi(H))$

2 \log (n)

$2\log(n)$

Jak działa naprawa O (1)? Jakie jest zastosowanie potencjalnej funkcji w naprawie sterty? Czy możesz wyjaśnić

— Sohaib

O (\log n)

$O(\log n)$

O (1)

$O(1)$

@ A. Schulz Tak więc w istocie oznacza to, że biorąc pod uwagę, że operacja wyodrębniania jest wykonywana n razy, ponieważ za każdym razem potencjalna funkcja zmniejsza się o 2 logn (może, ale nie musi wzrosnąć równomiernie po naprawie). Ogólna złożoność takiej rzeczy byłaby stała, ponieważ ostatecznie nie byłoby węzła w drzewie. Czy mam rację?

— Sohaib