Podstawową strukturą danych jest struktura "obsługująca" operacje Delete(x,S), Insert(x,S), dla zadanego zbioru S. Operacja delete pobiera z S i zwraca jako wartość "pewien" element S. Nie interesuje nas na razie, który element zostanie usunięty. Niedeterminizm pozwala nam użyć w takim wypadku jednej z kilku struktur danych, które omawiamy poniżej. W niektórych zastosowaniach istotne jest, który element jest pobierany, i wtedy nazwy operacji Insert i Delete często zmieniamy na nazwy bardziej odpowiadające terminologicznie tym strukturom. Będziemy jednak też używać nazewnictwa Delete, Insert, o ile nie prowadzi to do niejednoznaczności. Elementarne struktury danych, w których określone są operacje Insert, Delete, to:
Są one punktem wyjścia do bardziej skomplikowanych struktur, w szczególności różnego typu drzew.
Wariantem kolejki jest kolejka priorytetowa typu min. Jest to struktura danych, która "obsługuje" ciąg operacji insert, delete, gdzie operacja delete zawsze pobiera minimalny (maksymalny) element. Operację tę nazwiemy w tym przypadku DeleteMin (DeleteMax). Operacja delete jest tutaj w dużym stopniu zdeterminowana.
Załóżmy, że ciąg operacji Insert można podzielić na dwa ciągi następujące po sobie; w każdym z nich w operacji Insert wstawiamy elementy w porządku rosnącym. Wtedy kolejkę priorytetową można łatwo zaimplementować tak, by operacje Insert, Delete można było wykonać w czasie stałym.
Pokażemy na przykładzie algorytmu Optymalne-Sklejanie-Par zastosowanie tego typu kolejki priorytetowej. W algorytmie tym podstawową operacją jest:
zastąp dwa minimalne elementy \( a,b \) przez \( a+b \).
Operacja ta jest równoważna operacjom:
\( a = DeleteMin(S) \); \( b = DeleteMin(S) \); \( Insert(a+b,S) \);
W szczególnym przypadku, rozważonym poniżej, operacje Insert, DeleteMin można zaimplementować w czasie stałym. Załóżmy, że początkowy zbiór \( S \) jest posortowany i jego elementy są umieszczone na stosie \( ST \) w kolejności rosnącej (od szczytu "w dół"). Załóżmy, że mamy dodatkowo zwykłą kolejkę \( Q \) początkowo pustą. Wtedy ciąg operacji
\( a = DeleteMin(S) \); \( b = DeleteMin(S) \); \( Insert(a+b,S) \)
możemy wykonać w czasie stałym: element minimalny jest na wierzchołku \( ST \) lub na początku kolejki \( Q \), element \( a+b \) wstawiamy na koniec \( Q \). Zatem algorytm Optymalne-Sklejanie-Par możemy zaimplementować w czasie liniowym, gdy początkowy zbiór jest od razu posortowany. Widzimy na tym przykładzie, w jaki sposób złożoność algorytm zależy od struktury danych związanych z algorytmem.
W następujących dwóch przykładach możemy sobie pozwolić na niedeterministyczny wariant operacji Delete.
Przypuśćmy, że mamy funkcję \( f : \{1,2,\ldots n\}\rightarrow\{1,2,\ldots n\} \), zadaną tablicą \( f[1..n] \), i chcemy znaleźć rozmiar maksymalnego podzbioru, na którym ta funkcja jest bijekcją.
Jest to zadanie bardzo podobne. Mamy dwie częściowo określone funkcje \( f_1, f_2 \) ze zbioru \( [1..n] \) w siebie. Chcemy znaleźć taką permutację \( \pi = (i_1,i_2,\ldots i_n) \), żeby \( \pi(f_k(i)) > \pi(i), \forall \ 1\le i\le n,\ k=1,2 \), jeśli \( f_k(i) \) określone.
Oba te przykłady możemy wyrazić w terminach teorii grafów. Zbiorem wierzchołków jest tutaj zbiór \( [1..n] \). W pierwszym przykładzie krawędzie są postaci \( (i,f(i)) \), w drugim postaci \( (i,f_k(i) \), gdzie \( k=1,2 \).
W pierwszym przykładzie chcemy znaleźć maksymalny podzbiór grafu, na którym podgraf indukowany jest zbiorem cykli.
W drugim przypadku mamy szczególny przypadek tzw. sortowania topologicznego grafu. Wierzchołek nazywamy roboczym, gdy nie wchodzi do niego żadna krawędź. Niech \( S \) będzie początkowo zbiorem wszystkich wierzchołków roboczych. Algorytmy dla obu powyższych problemów działają w podobny sposób. Pobieramy element \( v \in S \), odpowiednio przetwarzamy i usuwamy z grafu. Wskutek usunięcia \( v \) pewne nowe wierzchołki stają się roboczymi i wstawiamy je do S. Kontynuujemy, dopóki S jest niepusty.
W przypadku problemu maksymalnej bijekcji po prostu usuwamy \( v \), a w przypadku numeracji \( \pi \) \( \pi(v) \) staje się kolejnym numerem. Pomimo interpretacji teorio-grafowej nie musimy implementować żadnej reprezentacji grafu: wszystko się dzieje w wejściowych tablicach i w dodatkowej tablicy licznik[v], w której trzymamy dla każdego \( v \) liczbę krawędzi aktualnie wchodzących do \( v \). Konkretną implementację pozostawiamy jako ćwiczenie. Zbiór S jest tutaj zbiorem wierzchołków roboczych, które są w pewnym sensie akcjami do wykonania. Do S wkładamy akcje, które mamy wykonać; kolejność nie jest istotna. S może być listą, stosem lub kolejką.
Rozważmy inny przykład algorytmu, którego złożoność istotnie zależy od (bardzo prostej) struktury danych (lista jednokierunkowa, która się zamienia w drzewo skierowane w stronę korzenia).
Przypuśćmy, że mamy na wejściu \( n \) trójek postaci \( [p,q,s] \), gdzie \( p,q \in \{1,2,\ldots,n\} , s\ge 0 \). Każdej trójce odpowiada funkcja \( f_{p,q,s} \) taka, że:
\( f_{p,q,s}(i)\ =\ s \), gdy \( p \le i \le q \), oraz \( f_{p,q,s}(i)\ =\ 0 \) w przeciwnym przypadku.
Naszym zadaniem jest dla każdego \( 1 \le i \le n \) obliczyć wartość \( F(i) \) będącą maksimum z danych funkcji \( f_{p,q,s} \) dla argumentu \( i \). Można podać następującą interpretację. Każda funkcja \( f_{p,q,s} \) opisuje kształt wieżowca w Warszawie patrząc z prawej strony Wisły. Wtedy funkcja \( F \) opisuje panoramę centrum Warszawy.
Załóżmy, że trójki \( (p,q,s) \) są posortowane ze względu na \( s \). Wtedy rozważamy kolejno funkcje \( f_{p,q,s} \) w kolejności rosnącego \( s \) i nadajemy za każdym razem końcowe wartości dla pozycji z przedziału \( [p,q] \), dla których jeszcze wartości nie są obliczone. Taki algorytm miałby złożoność kwadratową.
Początkowo elementy trzymamy w liscie jednokierunkowej, element i-ty wskazuje na (i+1)-szy dla i<n+1. Element n na n+1. Zakładamy więc, że mamy na przykład tablicę NEXT taką, że NEXT[i]=i+1, dla i<n+1, NEXT[n+1]=n+1, oraz początkowo Wynik[i]=0 dla każdego i. Trójki trzymamy w trzech tablicach, i-ta trójka jest dana przez P[i], Q[i], S[i]. Nasze podstawowe założenie:
tablica S jest posortowana malejąco
Jeśli przetwarzamy w kolejnej iteracji przedział \( [p,q] \), to zaczynamy od elementu p i poruszamy się na liście dopóki nie przekroczymy q, w tym momencie jesteśmy w jakimś elemencie r. Wszystkie elementy, które przeglądaliśmy, zmieniają swoje dowiązanie na r. W pewnym sensie możemy powiedzieć, że kompresujemy ścieżkę, którą przeszliśmy. Koszt iteracji to, z grubsza, długość ścieżki (liczba dowiązań, które się zmieniły). Z listy jednokierunkowej robi nam się drzewo jednokierunkowe.
Algorytm Panorama-Warszawy1
for i := 1 to n do j := P[i]; while j <= Q[i] do Wynik[j] := max( Wynik[j],S[i] ); j:=NEXT[j]; Kompresja ścieżki: k := P[i]; while k < j do pom :=NEXT[k]; NEXT[k] := j; k :=pom;
Algorytm ten powstał w ten sposób, że do algorytmu naiwnego doszyliśmy dodatkową część: Czaso-Przyspieszacz.
Dosyć łatwo pokazać, że czas tego algorytmu będzie rzędu co najwyżej \( n^{3/2} \), a więc lepszy niż algorytmu naiwnego. Jeśli "kompresujemy" ścieżkę długości k (w części Czaso-Przyspieszacz), to zmniejszamy sumaryczną odległość elementów do korzenia (elementu n) o wielkość co najmniej taką, jak suma liczb 1,2,3..,k, a więc mniej więcej o \( k^2 \). Początkowa suma jest rzędu \( n^{2} \). Za każdym razem zmniejszamy tę sumę o kwadrat kosztu danej iteracji.
Jeśli mamy n liczb, których kwadraty w sumie dają \( n^2 \), to suma tych liczb jest co najwyżej \( n^{3/2} \). Zapisując bardziej matematycznie:
Podobne algorytmy poznamy w module o problemie find-union, wtedy też będziemy mogli lepiej zanalizować algorytm rozwiązujący problem Panoramy.
Rozważmy jeszcze przypadek (nazwijmy go "specjalnym"), gdy wszystkie przedziały odpowiadające wejściowym funkcjom maja wspólne przecięcie teorio-mnogościowe. Nazwijmy ten przypadek specjalnym. Wtedy mamy bardzo prosty algorytm działający w czasie liniowym.
Algorytm Panorama-Warszawy2
lewy:=Q[1]+1; prawy:=Q[1]; for i := 1 to n do for j := lewy-1 downto P[i] do Wynik[j] := max( Wynik[j],S[i] ); for j := prawy+1 to Q[i] do Wynik[j] := max( Wynik[j],S[i] ); lewy:=min(lewy,P[i]), prawy:=max(prawy,Q[i]);
Dlaczego przypadek specjalny jest interesujący? Otóż wykorzystując algorytm dla tego przypadku, możemy łatwo otrzymać algorytm typu dziel i zwyciężaj działający w czasie \( O(n \log n) \).
Podzielmy przedział [1..n] na dwie połowy. Rozważmy najpierw tylko te wieżowce, których przedziały są całkowicie w lewej części. Stosujemy do nich algorytm rekurencyjny. Podobnie robimy dla prawej połowy. Zostają nam jeszcze wieżowce, których przedziały mają punkty wspólne z obu połówkami, a to jest właśnie przypadek specjalny, który rozwiązaliśmy w prosty sposób.
Pomimo tego wydaje się, że algorytm Panorama-Warszawy1 jest znacznie prostszy, gdyż nie wymaga rekursji ani specjalnych przypadków.
Działanie stosu i kolejki świetnie ilustrują różne warianty problemu sortowania z użyciem stosów i kolejek. Niech \( \pi \) będzie permutacją liczb \( \{1,2,\ldots n\} \). Możemy posortować \( \pi \) stosując niedeterministyczny algorytm:
while na wyjściu nie są wypisane wszystkie elementy do wykonaj dokładnie jedną z trzech instrukcji: (1) wstaw kolejny element pi(i) do jednej z kolejek; i=i+1 (2) lub wypisz pi(i) na wyjściu; i=i+1 (3) lub pobierz i wypisz na wyjściu pierwszy element jednej z kolejek
Zdefiniujmy liczbę kolejkową permutacji \( \pi \) jako minimalną liczbę kolejek potrzebnych do posortowania permutacji \( \pi \). Na przykład dla \( \pi=(1,2,3) \) liczba ta wynosi 0, a dla \( \pi=(3,2,1) \) wynosi 2.
Jak wyznaczyć liczbę kolejkową w czasie liniowym? Porównajmy ten problem z problemem maksymalnego malejącego podciągu. Pozostawiamy to jako ćwiczenie.
Podobnie definiujemy liczbę stosową. W tym wypadku w powyższym nieformalnym algorytmie zastępujemy kolejkę przez stos. Można również zdefiniować liczbę kolejkowo-stosową, pytając o minimalną liczbę stosów i kolejek, które razem posortują daną permutację. Jest to trudne pytanie.
W poprzedniej wersji sortowania każdy element może trafić tylko do jednej kolejki. Rozważmy teraz wersję, w której mamy \( k \) kolejek \( Q_1,Q_2,Q_3, \ldots Q_k \) i element może trafiać do kolejek o coraz mniejszych numerach.
Pojedyncza operacja polega na wstawieniu kolejnego elementu z \( \pi \) do jednej z kolejek, wypisaniu bezpośrednio na wyjście, o ile jest on pierwszym niepobranym elementem w \( \pi \) lub pierwszym elementem pewnej kolejki, albo przełożeniu pierwszego elementu pewnej kolejki \( Q_i \) do kolejki \( Q_j \) dla \( j < i \).
Można pokazać, że do posortowania każdej permutacji wystarczy logarytmiczna liczba kolejek.
Podobny fakt zachodzi, gdy kolejki zastąpimy stosami. Pozostawiamy ten problem (zarówno dla kolejek jak i dla stosów) jako ćwiczenie.
Załóżmy, że każdy element ciągu \( \pi \) jest początkowo listą jednoelementową. Oznaczmy zbiór tych list przez \( S \). Załóżmy też, że umiemy scalić dwie posortowane listy w czasie proporcjonalnym do sumy ich długości za pomocą operacji merge (patrz następne wykłady).
Algorytm Sortowanie-Kolejkowe-1
while |S| > 1 do lista1 := delete(S); lista2 := delete(S); insert(merge(lista1,lista2),S)
Pozostawiamy jako ćwiczenie pokazanie tego, że jeśli S jest kolejką, to algorytm ten działa w czasie \( O(n \log n) \), a jeśli \( S \) jest stosem, to algorytm działa w czasie kwadratowym. Widać na tym przykładzie przewagę kolejki nad stosem. Załóżmy, że mamy posortować tablicę \( A[0,1,\ldots, n-1] \) i \( n \) jest potęgą dwójki. Wtedy następujący algorytm wykonuje ten sam ciąg scaleń co algorytm Scalanie-Kolejkowe. Dowód tego pozostawiamy jako ćwiczenie.
Algorytm Sortowanie-Kolejkowe-2
Scalanie-Kolejkowe bez kolejki m := 1; while m < n do for i:=0 to n/(2m) do merge(A[i..i+m-1], A[i+m..i+2m-1]); m := 2m;