Opracuj sposób implementacji kolejki typu FIFO z pomocą dwóch stosów w taki sposób, żeby zamortyzowany koszt operacji stosowych był stały. Dokonaj analizy kosztu metodami księgowania i funkcji potencjału.
Reprezentujemy stos w dynamicznej tablicy \(S[1..n]\), gdzie \(n = 2^m\), dla pewnego całkowitego \(m \ge 0 \). Poszczególne operacje implementujemy następująco:
1 Ini:: //wykonywana tylko raz 2 begin 3 New(S[1..1]); 4 n := 1; k := 0; 5 end;
1 Push(e):: 2 begin 3 if k = n then 4 begin 5 New(T[1..2*n]); 6 for i := 1 to n do T[i] := S[i]; 7 dispose(S); 8 n := 2*n; 9 S := T 10 end; 10 k := k + 1; 11 S[k] := e 12 end;
1 Pop:: 2 begin 3 if k > 0 then 4 begin 5 e := T[k]; 6 k := k - 1 7 end; 8 if (n > 2) and (k = n/4) then 10 begin 11 New(T[1..n/2]); 12 for i := 1 to k do T[i] := S[i]; 13 dispose(S); 14 S := T; 15 n := n/2 15 end; 10 return e 11 end;
Załóżmy, że operacje alokacji i zwalniania pamięci wykonują się w czasie stałym. Zanalizuj koszt zamortyzowany operacji Push i Pop metodami księgowania i funkcji potencjału.
Dany jest spójny graf nieskierowany \(G=(V,E)\) z dodatnimi, całkowitoliczbowymi wagami na krawędziach oraz wyróżnione wierzchołki \( s \) i \( t \). Zaprojektuj algorytm, który spośród najlżejszych ścieżek pomiędzy \( s \) i \( t \) wyznaczy jedną, z najmniejszą liczbą krawędzi.
Dokonaj analizy kosztu pesymistycznego operacji DeleteMin, Insert oraz DecreaseKey na kopcach Fibonacciego.
Dokonaj analizy kosztu zamortyzowanego poszczególnych operacji w przypadku, gdy operacja DecreaseKey polega tylko na odcięciu węzła ze zmniejszanym kluczem od jego ojca i umieszczeniu go wraz ze swoim poddrzewem na liście korzeni.