Czy istnieje kolejka priorytetowa z wyciągami ?

46

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 ) $\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. $\mathcal{O}(n)$ $o\left(\frac{n}{\log n}\right)$

data-structures amortized-analysis priority-queues

— Alex ten Brink
źródło

Myślę, że użycie zrównoważonego BST, który nie przywróciłby równowagi podczas wykonywania Extract-Min może działać. A może lista pominięć.

— svick

@svick: listy pomijania są losowe, a nie tego szukam. Jeśli możesz to zrobić za pomocą BST, to świetnie, ale myślę, że będziesz musiał zrobić jakieś równoważenie.

— Alex ten Brink

Na marginesie: to jest zalążkowe pytanie i znam odpowiedź, ale miło jest widzieć, że nie tak łatwo ją rozwiązać. Jeśli ktoś zna odpowiedź, nie wahaj się jej udzielić :)

— Alex ten Brink

Jeśli akceptujesz amortyzowane czasy aktualizacji, możesz zachować standardowe struktury sterty i wprowadzać jedynie niewielkie zmiany w analizie. Zobacz moją odpowiedź poniżej.

— Joe

27

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.

— Raphael
źródło

2

Nie jest dla mnie jasne, jak uruchomić amortyzowaną analizę, jeśli nie użyjesz metody extractMin. Czy możesz dać wskazówkę?

— jbapple

Nie zrobiliśmy tego szczegółowo. Chodzi o to, że seria operacji wyodrębniania-min nie równoważy drzewa, dlatego nie jest konieczne rozstawianie i normalna analiza powinna działać dla wstawień.

— Raphael

9

Ostrożny! Splay drzewa niekoniecznie są zrównoważone. Węzły, które nie były dostępne przez długi czas, mogą znajdować się bardzo głęboko w drzewie. Aby analiza przejść, możesz mieć argumentować w warunkach tego samego potencjalnej funkcji używanych do analizy glifów.

— JeffE

20

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 . $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.

— Joe
źródło

1

Jak bardzo podstępnie. Masz rację, chyba powinienem był zażądać czegoś mocniejszego, aby to wykluczyć. Fajny pomysł :)

— Alex ten Brink

@AlextenBrink Możesz zażądać usunięcia najgorszym przypadku . (wydaje się, że o to chodziło w niektórych innych odpowiedziach) Do mojej odpowiedzi dodałem akapit, aby rozwiązać tę sprawę.

O (1)

$O(1)$

— Joe

14

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)$

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)$

— jbapple
źródło

8

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)$

— Alex ten Brink
źródło

Kluczowym wnioskiem jest to, że drzewa kozłów ofiarnych zapewniają, że usunięcie dowolnego węzła bez ponownego równoważenia nie wpływa na wydajność innych operacji w długim okresie, nawet jeśli usuniesz wiele węzłów.

— Raphael

Znam dwa sposoby usuwania w drzewach kozłów ofiarnych. Jeden sposób odzwierciedla wstawienia i jest zamortyzowanym czasem . Innym sposobem, w jaki słyszałem o globalnej przebudowie, jest amortyzacja , ale w tym przypadku nie wiem, jak utrzymać wątki. Wyobraź sobie, że wstawiasz nowy klucz do części drzewa, która zawiera wszystkie usunięte klucze, które mają zostać usunięte. Jak znaleźć poprzednika klucza do wstawienia w czasie ?

O (\lg n)

$O(\lg n)$

O (1)

$O(1)$

O (\lg n)

$O(\lg n)$

— jbapple

2

@jbapple: istnieją dwie odmiany sposobu usuwania w czasie drzewek kozłów ofiarnych . Jednym z nich jest pozostawienie węzła wewnątrz, oznaczenie go jako usuniętego i usunięcie wszystkich usuniętych węzłów za pomocą globalnej przebudowy, a drugim naprawdę usunięcie węzła. Pierwszy jest łatwiejszy do analizy (a także daje ci ograniczenie do drugiego, dlatego zwykle jest wyjaśniany), ale drugi jest tym, którego szukam: możesz usunąć w czasie w waniliowym drzewie wyszukiwania binarnego jeśli możesz wykonać zapytania poprzedzające / następcze w czasie , a równoważenie w czasie zamortyzowane daje resztę granicy.

O (1)

$O(1)$

O (1)

$O(1)$

O (1)

$O(1)$

O (1)

$O(1)$

— Alex ten Brink

Ach, rozumiem teraz.

— jbapple

2

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ści $\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 .

— Juho
źródło

Chociaż bardzo interesująca struktura danych, miękkie sterty nie są dokładne: findmin może zwrócić wartość, która nie jest minimalna, ale jest jedynie przybliżonym minimum. W każdym razie dzięki za linki :)

— Alex ten Brink

1

@AlextenBrink: celem struktury danych (podobnie jak wielu algorytmów probabilistycznych) jest to, że można użyć przybliżonej struktury danych, aby uzyskać dokładne odpowiedzi. Rzeczywiście przybliżona natura miękkich hałd nie przeszkodziła w zastosowaniu jej w jedynym znanym algorytmie liniowego czasu dla minimalnego drzewa rozpinającego.

— Jérémie

2

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 . $\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.

— W
źródło

2

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 . $\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ść. $\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 ). $\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.

— W
źródło

1

Masz na myśli drzewo AVL lub podobne zrównoważone drzewo? W jaki sposób upewniasz się, że usunięcie minimum nie powoduje więcej niż stale wielu rotacji dalej niż stale wielu kroków od (od miejsca usuwania lub korzenia)? W szczególności usunięcie elementów z drzew AVL może powodować obrót , więc musisz spierać się, jak temu zapobiec.

O (\log n)

$O(\log n)$

— Raphael

Co oznacza „wątek binarnego drzewa wyszukiwania w tablicy”?

— jbapple

@AT: Podzielam sentyment jbapple.

— Raphael

Przechowywanie drzewa binarnego w tablicy w ten sposób (podobnie jak klasyczna sterta binarna) powoduje, że każdy obrót zajmuje czas, gdzie jest rozmiarem poddrzewa zakorzenionego w obróconym węźle. W takim przypadku robienie „tylko” rotacji podczas aktualizacji wciąż może zająć dużo czasu.

Ω (k)

$\Omega(k)$

k

$k$

O (1)

$O(1)$

— jbapple

Twoja aktualizacja, w której wyjaśnisz, jak wdrażać rotacje w stałym czasie, nie działa w tablicach. Ta odpowiedź jest nadal niepoprawna. Dokument Tarjan, do którego się odwołujesz, dotyczy drzew przechowywanych z węzłami i wskaźnikami.

— jbapple,

-2

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})$ .

— W
źródło

Chociaż dokument, który podłączyłeś, jest interesujący, kolejka priorytetowa, którą prezentują, nie ma ciągłego usuwania czasu (jeśli poprawnie czytam streszczenie), a zatem nie jest tym, o co proszę.

— Alex ten Brink

-2

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

Utwórz listę z dowolnej (stałej) liczby elementów, powiedzmy 6: $\mathcal{O}(1)$
Posortuj listę: = $\mathcal{O}(6)$ $\mathcal{O}(1)$
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_{size - 1}) \lor (k < n_{0}) \lor ((k < n_{i}) \land (k > n_{i + 1})))$ $((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 .

— W
źródło

2

Czas wstawiania jest daleko od znaku.

— Raphael

To jest zbyt szkicowe. Na przykład, co to jest , , and ?

n_{s i z e - 1}

$n_{size-1}$

n_{0}

$n_0$

n_{i}

$n_i$

n_{i + 1}

$n_{i+1}$

— Juho

Czytając streszczenie artykułu, który łączysz, wydaje się, że te granice są oczekiwanymi granicami dla danych wejściowych określonego rozkładu, a zatem nie tego szukam: chcę granic, o których wspominam na dowolnym wejściu.

— Alex ten Brink

@Raphael: Nie, nie jest. mrm: pozycje na liście. AlextenBrink: Można go łatwo zmienić na najgorszy przypadek w dowolnej dystrybucji za pomocą algorytmu wyszukiwania binarnego w celu znalezienia punktu wstawienia.

O (l o g n)

$\mathcal{O}(log\ n)$

— AT

@AT Logarytmiczne wyszukiwanie binarne wymaga dostępu losowego. Jaka jest implementowana lista bazowa jako? Naprawdę powinieneś się kłócić o swoje granice. Również „pozycje na liście” są niejasne - do jakich pozycji i do czego odnoszą się symbole? Nie każdy ma dostęp do połączonego papieru. Postaraj się, aby twoja odpowiedź (więcej) była niezależna i przynajmniej podsumuj fakty. W tym momencie nie wierzę, że twoja odpowiedź jest poprawna.

— Juho,