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 2 log ( n ) lub ∑ n k = 1 2 log ( k ) )$\lfloor \log(n) \rfloor$$2\log(n)$$\sum_{k=1}^n 2\log(k)$

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

Masę elementu ı w stosie H 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$

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

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