Czy istnieje kolejka priorytetowa z wyciągami ?

Istnieje wiele struktur danych, które implementują interfejs kolejki priorytetowej:

• Wstaw: wstaw element do struktury
• Get-Min: zwraca najmniejszy element w strukturze
• Extract-Min: usuń najmniejszy element ze struktury

Typowe struktury danych implementujące ten interfejs to (min) hałdy .

Zazwyczaj (zamortyzowane) czasy wykonywania tych operacji są następujące:

• Wstaw: (czasami )O ( log n $\mathcal{O}(1)$$\mathcal{O}(\log n)$
• Get-Min:$\mathcal{O}(1)$
• Extract-Min:$\mathcal{O}(\log n)$

Na przykład sterta Fibonacciego osiąga te czasy działania. Teraz moje pytanie jest następujące:

Czy istnieje struktura danych o następujących (zamortyzowanych) czasach działania?

• Wstaw:$\mathcal{O}(\log n)$
• Get-Min:$\mathcal{O}(1)$
• Extract-Min:$\mathcal{O}(1)$

Jeśli możemy zbudować taką strukturę w czasie przy danym posortowanym wejściu, możemy na przykład znaleźć przecięcia linii na wstępnie posortowanych danych wejściowych z skrzyżowania są szybsze niż w przypadku użycia „zwykłych” kolejek priorytetowych.o ( $\mathcal{O}(n)$$o\left(\frac{n}{\log n}\right)$

Naszym pomysłem jest użycie gwintowanych drzew rozstawczych . Poza artykułem z Wikipedii powleczymy drzewa tak, aby każdy węzeł miał wskaźnik nextdo swojego następcy w kolejności przechodzenia; trzymamy również wskaźnik startdo najmniejszego elementu w drzewie.

Łatwo zauważyć, że wyodrębnienie najmniejszego elementu jest możliwe w (najgorszym przypadku) czasie : wystarczy podążać za wskaźnikiem, usunąć minimum i zmienić wskaźnik na minimum . Minimum nigdy nie może mieć pozostawionego dziecka; jeśli ma odpowiednie dziecko, umieszczamy je na minimalnym miejscu w drzewie. Mamy nie wykonywać drzew operacja splay splay zwykle zrobi. W rezultacie powstaje drzewo wyszukiwania, które jest nadal dość zrównoważone: ponieważ usuwamy tylko węzły z lewej flanki, wiemy, że gdy liczba węzłów (w dotkniętym poddrzewie) spada do około połowy pierwotnej liczby z powodu usunięcia, (sub ) wysokość drzewa zmniejsza się o jeden.$\mathcal{O}(1)$startnext

Możliwe są wstawienia w zamortyzowanym czasie; operacje zygzakowate (a co nie) również tutaj ładnie zrównoważą drzewo.$\mathcal{O}(\log n)$

W najlepszym razie jest to szorstki szkic. Podziękowania należą się F. Weinbergowi, który zastanawiał się nad tym pytaniem ze mną i naszym doradcą M. Nebelem, który wspomniał o drzewach splay, o jedynym wariancie drzewa, którego nie próbowaliśmy.

• Wstaw:$\mathcal{O}(\log n)$
• Get-Min:$\mathcal{O}(1)$
• Extract-Min:$\mathcal{O}(1)$

Amortyzowany czas

Proste implementacje kolejki priorytetowej (np. Dowolnego zbalansowanego BST lub standardowej binarnej min-sterty) mogą osiągnąć te (zamortyzowane) czasy działania po prostu obciążając koszt Extract-Min do wstawienia i utrzymując wskaźnik na minimum elementu. Na przykład możesz mieć potencjalną funkcję . Następnie wstawienie nowego elementu zwiększa potencjał o , więc zamortyzowany koszt wstawienia nadal wynosi , ale Extract-Min () zmniejsza potencjał o , i więc zamortyzowany koszt to tylko .O ( log n ) O ( log n ) Ω ( log n ) O ( 1 $cn \log n$$O(\log n)$$O(\log n)$$\Omega(\log n)$$O(1)$

Najgorszy przypadek

Możesz użyć istniejącej struktury danych w literaturze: drzewa wyszukiwania palcami i po prostu utrzymywać wskaźnik na minimalnym elemencie. Zobacz tę ankietę, aby uzyskać przegląd, oraz artykuł z 1988 r. Autorstwa Levcopoulos i Overmars, aby znaleźć możliwą do wdrożenia wersję, która spełnia Twoje potrzeby.

2-4 drzewa amortyzowały modyfikacje w znanych lokalizacjach. To znaczy, jeśli masz wskaźnik do jakiegoś miejsca w drzewie, możesz usunąć lub dodać tam element w zamortyzowanym czasie .O ( 1 $O(1)$$O(1)$

W ten sposób możesz po prostu utrzymać wskaźnik do minimalnego elementu i węzła głównego w drzewie 2-4. Wkładki powinny przechodzić przez węzeł główny. Aktualizacja wskaźnika do minimum jest trywialna po deleteMin, a deleteMins to czas (amortyzowany).$O(1)$

Ciekawa uwaga: czerwono-czarne drzewa to tylko sposób patrzenia na 2-4 drzewa. Projektanci standardu C ++ 98 spodziewali się, że implementatorzy bibliotek dostarczą kontener oparty na drzewie czerwono-czarnym, a standard określa, że ​​wstawianie i usuwanie powinno być amortyzowane przez w znanych lokalizacjach (które nazywają „iteratorami” ). Jest to jednak o wiele trudniejsze w przypadku czerwono-czarnych drzew niż w przypadku 2-4 drzew, ponieważ wymaga leniwego oznaczania węzłów, które należy ponownie pokolorować. O ile mi wiadomo, żadne implementacje standardowej biblioteki C ++ 98 nie spełniły tego szczególnego wymagania.$O(1)$

Na życzenie oto struktura, którą znalazłem po sformułowaniu pytania:

Podstawową ideą jest użycie gwintowany drzewa kozioł ofiarny wraz ze wskaźnikiem do minimum (i na dokładkę, maksimum, jak również). Prostszą alternatywą dla wątków jest utrzymanie wskaźników poprzedzających i następczych w każdym węźle (co jest równoważne, prostsze, ale ma więcej narzutu). Przyszedłem nazwać to kupą kozła ofiarnego , żeby nadać mu jakąś nazwę.

Właśnie ta podstawowa struktura zapewnia następujące operacje:

• Szukaj: podany klucz zwraca wskaźnik do odpowiedniego węzła w czasie .$\mathcal{O}(\log n)$
• Wstaw: dany klucz wstawia klucz do struktury, zwracając wskaźnik do tego węzła w czasie .$\mathcal{O}(\log n)$
• Poprzednik / następca: dany wskaźnik zwraca następcę lub poprzednika w czasie .$\mathcal{O}(1)$
• Get-Min / Max: przywraca wskaźnik do minimum lub maksimum.

W analizie drzewek kozłów ofiarnych obciążenie związane z usunięciem jest analizowane jako , ale analiza faktycznie daje obciążenie równoważące (co jest ignorowane w pracy ponieważ liczą także czas potrzebny na znalezienie węzła, który ma zostać usunięty). Jeśli więc mamy wskaźnik do węzła, możemy go usunąć w stałym czasie (możesz to zrobić w wątkowym drzewie wyszukiwania binarnego w czasie ) i w połączeniu z z równoważeniem, daje to czas usunięcia:$\mathcal{O}(\log n)$$\mathcal{O}(1)$$\mathcal{O}(\log n)$$\mathcal{O}(1)$$\mathcal{O}(1)$$\mathcal{O}(1)$

• Usuń: dany wskaźnik usuwa węzeł w czasie .$\mathcal{O}(1)$

Łącząc to:

• Extract-Min / Max: usuwa minimalny / maksymalny węzeł w czasie .$\mathcal{O}(1)$

Możesz zrobić trochę więcej ze wskaźnikami: na przykład nie jest trudno utrzymać wskaźnik do mediany lub innej statystyki porządku, więc możesz zachować stałą liczbę takich wskaźników, jeśli ich potrzebujesz.

Niektóre inne rzeczy:

• Konstruuj: biorąc pod uwagę kluczy w posortowanej kolejności, zbuduj stertę kozła ofiarnego w czasie.$n$$\mathcal{O}(n)$
• Równowaga: zrównoważ drzewo tak, aby tworzyło idealnie zrównoważone drzewo wyszukiwania binarnego (redukuje narzut związany z wyszukiwaniem) w czasie (możesz to zrobić o stały współczynnik szybciej niż sugeruje papier, wykorzystując wskaźników poprzednika / następcy).$\mathcal{O}(n)$

I wreszcie, jestem prawie pewien, że możesz wesprzeć te operacje, ale muszę się nad nimi zastanowić, zanim na pewno się o tym dowiesz:

• Insert-New-Min / Max: dany klucz, który jest mniejszy / większy niż jakikolwiek klucz już w strukturze, wstawia klucz do struktury, zwracając wskaźnik do tego węzła w czasie .$\mathcal{O}(1)$

Miękka kupa to subtelna modyfikacja dwumianowej kolejki. Struktura danych jest przybliżona z parametrem błędu . Obsługuje wstawianie, usuwanie, łączenie i findmin. Zamortyzowany złożoność każdej operacji , za wyjątkiem wkładki, odbywa czasu. Nowością miękkiej sterty jest pokonanie logarytmu związanego ze złożonością sterty w modelu opartym na porównaniu. Aby przełamać barierę teoretyczną informacji, entropię struktury danych zmniejsza się poprzez sztuczne podniesienie wartości niektórych kluczy. Nazywa się to niszczeniem kluczy. Struktura danych jest w pełni oparta na wskaźnikach (bez tablic ani założeń numerycznych) i jest optymalna dla dowolnej wartościO ( 1 ) log ( 1 / ϵ ) $\epsilon$$O(1)$$\log (1/\epsilon)$$\epsilon$ w modelu porównawczym.

Zastosowania miękkiej sterty obejmują obliczanie minimalnego drzewa opinającego dla wykresu, dynamiczne utrzymywanie percentyli i statystyki liniowego porządku czasowego. Może być również wykorzystywany do obliczeń przybliżonych, takich jak sortowanie przybliżone, w którym pozycja elementu nigdy nie różni się więcej niż od prawdziwej pozycji.$\epsilon n$

Oryginalny, przejrzysty i ładnie napisany artykuł patrz Bernard Chazelle, The Soft Heap: An Approximate Priority Queue with Optimal Error Rate, Journal of the ACM, 47 (6), str. 1012-1027, 2000 . Alternatywne wdrożenie i analiza, które według SODA'09 są prostsze i bardziej intuicyjne, patrz Kaplan H. & Zwick U., Prostsze wdrożenie i analiza miękkich hałd Chazelle, 2009 .

Okej, w końcu dostałem złożoność, której szukałeś, a co najlepsze, znalazłem ją w literaturze:

Złożoność najgorszego przypadku

Usuń :$\bf\mathcal{O}(1)$

Delete-min :$\bf\mathcal{O}(1)$

Find-min :$\bf\mathcal{O}(1)$

Wstaw :$\bf\mathcal{O}(log\ n)$

Odniesienie

JEŻELI MELD może zająć czas liniowy, możliwe jest wsparcie DELETE-MIN w najgorszym przypadku stałego czasu za pomocą drzewek wyszukiwania Dietz i Ramana [3]. Używając ich struktury danych MAKEQUEUE , FINDMIN , DELETEMIN , DELETE mogą być obsługiwane w najgorszym przypadku , WSTAW w najgorszym przypadku i MELD w najgorszym przypadku .O ( l o g n ) O ( n $\mathcal{O}(1)$$\mathcal{O}(log\ n)$$\mathcal{O}(n)$

Brodal, Gerth Stølting. „Szybkie zgrzewalne kolejki priorytetowe”. W materiałach z IV międzynarodowych warsztatów na temat algorytmów i struktur danych, 282–290. WADS '95. Londyn, Wielka Brytania, Wielka Brytania: Springer-Verlag, 1995.

[3]: Dietz, Paul F. i Rajeev Raman. „Drzewo ciągłej aktualizacji palca wyszukiwania”. Listy przetwarzania informacji 52, nr 3 (1994): 147–154.

Chociaż wykorzystuje to model obliczeniowy pamięci RAM :

Nasza struktura danych wykorzystuje model maszyny o dostępie swobodnym (RAM) z miarą kosztów jednostkowych i logarytmicznym rozmiarem słowa;

Niedawno podano model rozwiązania obliczeniowego typu Pointer-Machine[1] .

[1]: Brodal, Gerth Stølting, George Lagogiannis, Christos Makris, Athanasios Tsakalidis i Kostas Tsichlas. „Optymalne drzewa wyszukiwania palcem w maszynie wskaźnikowej”. J. Comput. Syst. Sci. 67, nr 2 (wrzesień 2003): 381–418.

Podejście do tego problemu poprzez utrzymanie dwóch struktur danych: macierzy i drzewa binarnego.

Aby utrzymać indeksowanie w tablicy, wcześniej byłeś związany ; ale ostatnio udało się temu zaradzić, modyfikując analizę techniki chronogramu. Nowa granica [niższa] została udowodniona dla podobnych problemów w modelu 1 sonda-komórka . Z lektury tego artykułu; rozumiem, że ta granica dotyczy również problemu reprezentacji listy .Ω(logn$\Omega(\dfrac{\log n}{\log\log n})$$\Omega(\log n)$

Teraz, jeśli włączysz drzewo binarne do swojej tablicy i ponownie zbalansujesz + reindeksuj co aktualizacje, będziesz miał: złożoność.O ( log n $\mathcal{O}(\log n)$$\mathcal{O}(\log n)$

Twój najdłuższy bieg - po nullusuniętych elementach - będzie . To oczywiście nie pozostawia teoretycznej przewagi nad ponownym równoważeniem + ponownym indeksowaniem każdej aktualizacji.$\mathcal{O}(\log n)$

W zależności od dystrybucji możesz założyć, że ponownie równoważą tylko każdą wkładkę; w ten sposób wyciągnij złożoność z ekstraktu. Wyciąg - z dowolnego końca - zajmie wtedy tylko ; ponieważ reindex nie musi wystąpić (wystarczy śledzić przesunięcia indeksu, aby zachować je w ).O ( 1 $\mathcal{O}(1)$$\mathcal{O}(1)$

Jeśli nie możesz przyjąć tego założenia, moje podejście pozostawi ci wstawianie, ponowne równoważenie i wyodrębnianie. Ma jednak przewagę nad niektórymi innymi podejściami, ponieważ można uzyskać min / maks i gdziekolwiek pomiędzy - np. Podać mi wartość mediany - w . Dodatkowo ma funkcjonalność.$\mathcal{O}(\log n)$$\mathcal{O}(1)$delete_at(idx)

1 Patrascu, Mihai i Erik D. Demaine. „Logarytmiczne dolne granice w modelu sondy komórkowej.” SIAM J. Comput. 35, nr 4 (kwiecień 2006 r.): 932–963. doi: 10.1137 / S0097539705447256.

Find-min w z oczekiwanym czasem aktualizacji$O(1)$$O(\sqrt{log\text{ }log\text{ }n})$

Zobacz artykuł z 2007 r .: Równoważność między kolejkami priorytetowymi a sortowaniem według Mikkel Thorup.

Uwaga: odwołuje się do artykułu Han & Thorup z 2002 r .: Sortowanie liczb całkowitych w Oczekiwany czas i przestrzeń liniowa$O(n\text{ }\sqrt{log\text{ }log\text{ }n})$ .

Analiza

Wstaw :$\mathcal{o}(n\ log\ log\ n)$

Wyszukaj :$\mathcal{o}(log\ log\ n)$

Usuń :$\mathcal{O}(1)$

Spacja :$\mathcal{O}(n)$

Get-Min :$\mathcal{O}(1)$

Extract-Min :$\mathcal{O}(1)$

Realizacja

1. Utwórz listę z dowolnej (stałej) liczby elementów, powiedzmy 6:$\mathcal{O}(1)$
2. Posortuj listę: =$\mathcal{O}(6)$$\mathcal{O}(1)$
3. Punkt wstawienia dla każdego kolejnego węzła będzie drugim elementem (') pos (-1 dla <, +1 dla> i z dwoma argumentami zależy od tego, od którego zaczynasz / kończysz w: i zostanie znaleziony przy użyciu interpolacji dynamicznej Wyszukaj [1] w:$k$$\pm$ $$((k > n_{\text{size}-1}) \lor (k<n_{0}) \lor ((k<n_{i}) \land (k>n_{i+1})))$$ $\mathcal{o}(log\ log\ n)$

[1]: Andersson, Arne i Christer Mattsson. „Dynamiczne wyszukiwanie interpolacji w czasie O (log log n)”. W Automata, Languages ​​and Programming, red. Andrzej Lingas, Rolf Karlsson i Svante Carlsson, 700: 15–27. Wykład notatki z informatyki. Springer Berlin / Heidelberg, 1993. http://dx.doi.org/10.1007/3-540-56939-1_58 .