Kolejka do kubełków

Kolejka zasobników
Tablica zasobników, odpowiednia dla priorytetów w zakresie od 1 do 6. Element o minimalnym priorytecie znajduje się w skrajnym lewym niepustym zasobniku.
Typ	kolejka priorytetowa
Wynaleziony	1969
Wynalezione przez	Robert Dial
Złożoność czasowa w notacji dużego O
Algorytm Przeciętny Najgorszy przypadek Wstawić O (1) O (1) Znajdź min O (#priorytety) O (#priorytety) Usuń min O (#priorytety) O (#priorytety) Klawisz zmniejszania O (1) O (1)

Kolejka kubełkowa to struktura danych , która implementuje abstrakcyjny typ danych kolejki priorytetowej : utrzymuje dynamiczną kolekcję elementów z numerycznymi priorytetami i umożliwia szybki dostęp do elementu o minimalnym (lub maksymalnym) priorytecie. W kolejce zasobnika priorytety muszą być liczbami całkowitymi i jest to szczególnie przydatne w zastosowaniach, w których priorytety mają mały zakres. Kolejka zasobników ma postać tablicy zasobników: tablicowej struktury danych , indeksowanej według priorytetów, której komórki zawierają kolekcje elementów o takim samym priorytecie. Przy takiej strukturze danych wstawianie elementów i zmiana ich priorytetu zajmuje stały czas . Wyszukiwanie i usuwanie elementu o minimalnym priorytecie zajmuje czas proporcjonalny do liczby zasobników lub, utrzymując wskaźnik do ostatnio znalezionego zasobnika, w czasie proporcjonalnym do różnicy priorytetów między kolejnymi operacjami.

Kolejka zasobników jest odpowiednikiem kolejki priorytetowej sortowania szufladkowego (zwanego także sortowaniem zasobnikowym), algorytmu sortowania, który umieszcza elementy w zasobnikach indeksowanych według ich priorytetów, a następnie łączy zasobniki. Użycie kolejki kubełkowej jako kolejki priorytetowej w sortowaniu przez wybór daje formę algorytmu sortowania szufladkowego. Kolejki zasobników są również nazywane kolejkami priorytetowymi zasobników lub kolejkami priorytetowymi o ograniczonej wysokości . Gdy są używane do skwantyzowanych przybliżeń do liczb rzeczywistych , są one również nazywane nieporządnymi kolejkami priorytetów lub kolejkami pseudopriorytetów . Są one ściśle powiązane z kolejką kalendarza , strukturą, która wykorzystuje podobną tablicę zasobników do dokładnego ustalania priorytetów według liczb rzeczywistych.

Zastosowania kolejki kubełkowej obejmują obliczanie degeneracji grafu , szybkie algorytmy dla najkrótszych ścieżek i najszerszych ścieżek dla grafów o wagach, które są małymi liczbami całkowitymi lub są już posortowane, oraz algorytmy zachłannej aproksymacji dla problemu zestawu pokrycia . Skwantyzowana wersja struktury została również zastosowana do szeregowania i maszerujących kostek w grafice komputerowej . Pierwsze użycie kolejki kubełkowej miało miejsce w algorytmie najkrótszej ścieżki autorstwa Dial (1969) .

Operacja

Podstawowa struktura danych

Kolejka kubełkowa może obsługiwać elementy o priorytetach całkowitych w zakresie od 0 lub 1 do pewnej znanej granicy C oraz operacje, które wstawiają elementy, zmieniają priorytet elementów lub wyodrębniają (znajdują i usuwają) element, który ma minimalną (lub maksymalny) priorytet. Składa się z tablicy A kontenerowych struktur danych ; w większości źródeł kontenery te są podwójnie połączonymi listami , ale alternatywnie mogą to być tablice dynamiczne lub zestawy dynamiczne . Kontener w p -tej komórce tablicy A [ p ] przechowuje zbiór elementów, których priorytetem jest p .

Kolejka zasobnika może obsłużyć następujące operacje:

• Aby wstawić element x z priorytetem p , dodaj x do kontenera w A [ p ] .
• Aby zmienić priorytet elementu, usuń go z kontenera dla jego starego priorytetu i włóż go ponownie do kontenera dla jego nowego priorytetu.
• Aby wyodrębnić element z minimalnym lub maksymalnym priorytetem, wykonaj sekwencyjne wyszukiwanie w tablicy, aby znaleźć odpowiednio pierwszy lub ostatni niepusty kontener, wybierz dowolny element z tego kontenera i usuń go z kontenera.

W ten sposób wstawianie i zmiany priorytetów zajmują stały czas, a wydobycie elementu o minimalnym lub maksymalnym priorytecie zajmuje czas O ( C ) .

optymalizacje

W ramach optymalizacji struktura danych może rozpoczynać każde sekwencyjne wyszukiwanie niepustego zasobnika od ostatnio znalezionego niepustego zasobnika zamiast od początku tablicy. Można to zrobić na dwa różne sposoby, leniwie (opóźniając te sekwencyjne wyszukiwania, dopóki nie będą one konieczne) lub z zapałem (przeprowadzając wyszukiwania z wyprzedzeniem). Wybór, kiedy przeprowadzić wyszukiwanie, wpływa na to, które operacje struktury danych są spowalniane przez te wyszukiwania. Oryginalna wersja struktury Dial wykorzystywała leniwe wyszukiwanie. Można to zrobić, utrzymując indeks L , który jest dolną granicą minimalnego priorytetu dowolnego elementu znajdującego się obecnie w kolejce. Podczas wstawiania nowego elementu L należy zaktualizować do minimum jego starej wartości i priorytetu nowego elementu. Podczas wyszukiwania elementu o minimalnym priorytecie wyszukiwanie może rozpocząć się od L zamiast od zera, a po wyszukaniu L należy pozostawić równe priorytetowi, który został znaleziony podczas wyszukiwania. Alternatywnie, chętna wersja tej optymalizacji L , tak aby zawsze wskazywało na pierwsze niepuste wiadro. Podczas wstawiania nowego elementu o priorytecie mniejszym niż L struktura danych ustawia L na nowy priorytet, a podczas usuwania ostatniego elementu z zasobnika o priorytecie L wykonuje sekwencyjne przeszukiwanie większych indeksów aż do znalezienia niepustego zasobnika i ustawienie L na priorytet wynikowego segmentu.

W każdym z tych dwóch wariantów każde kolejne wyszukiwanie zajmuje czas proporcjonalny do różnicy między starą i nową wartością L . Może to być znacznie szybsze niż O ( C ) dla wyszukiwań w niezoptymalizowanej wersji struktury danych. W wielu zastosowaniach kolejek priorytetowych, takich jak algorytm Dijkstry , minimalne priorytety tworzą sekwencję monotoniczną , co pozwala na użycie monotonicznej kolejki priorytetowej . W tych aplikacjach, zarówno dla leniwych, jak i chętnych wariantów zoptymalizowanej struktury, sekwencyjne wyszukiwanie niepustych zasobników obejmuje rozłączne zakresy zasobników. Ponieważ każdy segment mieści się co najwyżej w jednym z tych zakresów, ich liczba kroków sumuje się co najwyżej do C . Dlatego w tych aplikacjach całkowity czas sekwencji n operacji wynosi O ( n + C ) , a nie wolniejsze ograniczenie czasowe O ( nC ) , które wynikałoby bez tej optymalizacji. Odpowiednią optymalizację można zastosować w aplikacjach, w których kolejka zasobników jest używana do wyszukiwania elementów o maksymalnym priorytecie, ale w tym przypadku powinna ona utrzymywać indeks, który przekracza górną granicę maksymalnego priorytetu, a sekwencyjne wyszukiwanie niepustego zasobnika powinno być kontynuowane w dół od tej górnej granicy.

Inna optymalizacja (podana już przez Dial 1969 ) może być wykorzystana do zaoszczędzenia miejsca, gdy priorytety są monotoniczne i w całym przebiegu algorytmu zawsze mieszczą się w zakresie wartości r , zamiast rozciągać się na cały zakres od 0 do C. W takim przypadku można zindeksować tablicę według modulo r priorytetów , a nie według ich rzeczywistych wartości. Poszukiwanie elementu minimalnego priorytetu powinno zawsze rozpoczynać się od poprzedniego minimum, aby uniknąć priorytetów, które są wyższe od minimum, ale mają niższe moduły. W szczególności pomysł ten można zastosować w algorytmie Dijkstry na grafach, których długości krawędzi są liczbami całkowitymi z zakresu od 1 do r .

Ponieważ utworzenie nowej kolejki zasobników wymaga zainicjowania tablicy pustych zasobników, ten krok inicjalizacji zajmuje czas proporcjonalny do liczby priorytetów. Odmiana kolejki zasobników opisana przez Donalda B. Johnsona w 1981 r. Zamiast tego przechowuje tylko niepuste zasobniki na połączonej liście, posortowane według ich priorytetów, i wykorzystuje pomocnicze drzewo wyszukiwania, aby szybko znaleźć pozycję na tej połączonej liście dla każdego nowego wiadra. Potrzeba czasu O (log log C ) , aby zainicjować tę wariantową strukturę, stałego czasu, aby znaleźć element z minimalnym lub maksymalnym priorytetem oraz czasu O (log log D ) , aby wstawić lub usunąć element, gdzie D jest różnicą między najbliższym mniejsze i większe priorytety do priorytetu wstawianego lub usuwanego elementu.

Przykład

$priorytetami$ , liczbami 0, 1, 2 i 3. Składa się ona z tablicy, z której zawiera cztery komórki, początkowo puste. Dla celów tego przykładu można zapisać jako sekwencję czterech zestawów w nawiasach: $ZA$$\ pusty zestaw, \ pusty zestaw, \pustyzbiór ]}$ . Rozważ sekwencję operacji, w której wstawimy dwa elementy i ${$$\ displaystyle y}$ z tym samym priorytetem 1, wstawimy trzeci element $displaystyle z$ priorytetem 3, zmienimy priorytet $} \displaystyle x}$ na 3, a następnie wykonaj dwie ekstrakcje elementu o minimalnym priorytecie.

• Po wstawieniu z $1$ , ${\ Displaystyle A = [\ pusty zestaw, \ {x \}, \ pusty zestaw, \ pusty zestaw ]}$ .
• ${\ Displaystyle y}$ z priorytetem 1, ${\ Displaystyle A = [\ pusty zestaw, \ {x, y \} \ pusty zestaw, \ pusty zestaw ] }$ .
• Po wstawieniu z z priorytetem 3 ${\ Displaystyle A = [\ pusty zestaw, \ {x, y \}, \ pusty zestaw, \ {z \}] }$ .
• ${\ Displaystyle A = [\ pusty zbiór, \ {y \}, \ pusty zbiór, \ {x, z \}]}$ priorytetu x z 1 na trzy polega na usunięciu go z $]}$ { $3$ , po czym .
• $Displaystyle$ priorytecie w podstawowej wersji kolejki zasobnika przeszukuje od początku w celu znalezienia pierwszego niepustego elementu: $A [0]}$ jest pusty, ale ZA {\ displaystyle A} ${\ Displaystyle A [1] = \ {y \}}$ , niepusty zestaw. Wybiera dowolny element tego zestawu (jedyny element $jako$ element o minimalnym priorytecie. Usunięcie ${\ Displaystyle y}$ ze struktury pozostawia ${\ Displaystyle A = [\ pusty zestaw, \ pusty zestaw, \ pusty zestaw, \ {x, z \}]}$ .
• Druga operacja wyodrębniania, w podstawowej wersji kolejki zasobnika, przeszukuje ponownie od początku tablicy: ${\ Displaystyle A [0] = \ pusty zbiór}$ , ${\ Displaystyle A [1] = \ pusty zestaw$ , ${\ Displaystyle A [2] = \ pusty zbiór}$ , ${\ Displaystyle A [3] = {}}$ niepusty. W ulepszonych wariantach kolejki zasobnika wyszukiwanie rozpoczyna się zamiast tego od ostatniej pozycji, która okazała się niepusta, ${\ Displaystyle A [1]}$ . W $przypadkach$ pierwszy Jeden z jego elementów jest wybierany arbitralnie jako element o minimalnym priorytecie; na przykład można wybrać ${\ displaystyle z} .$ Ten element jest usuwany, pozostawiając ${\ Displaystyle A = [\ pusty zestaw, \ pusty zestaw, \ pusty zestaw, \ {x \}]}$ .

Aplikacje

Degeneracja wykresu

Kolejka kubełkowa może służyć do utrzymywania wierzchołków grafu nieskierowanego , uszeregowanych według ich stopni , oraz do wielokrotnego znajdowania i usuwania wierzchołków o minimalnym stopniu. Ten zachłanny algorytm można wykorzystać do obliczenia degeneracji danego grafu, równej największemu stopniowi dowolnego wierzchołka w momencie jego usunięcia. Algorytm przyjmuje czas liniowy , z optymalizacją lub bez optymalizacji, która utrzymuje dolną granicę minimalnego priorytetu, ponieważ każdy wierzchołek znajduje się w czasie proporcjonalnym do jego stopnia, a suma wszystkich stopni wierzchołków jest liniowa w stosunku do liczby krawędzi wykresu.

Algorytm Diala dla najkrótszych ścieżek

W algorytmie Dijkstry dla najkrótszych ścieżek w grafach skierowanych z wagami krawędzi, które są dodatnimi liczbami całkowitymi, priorytety są monotoniczne, a monotoniczna kolejka zasobników może być wykorzystana do uzyskania ograniczenia czasowego O ( m + dc ) , gdzie m jest liczbą krawędzi , d to średnica sieci, a c to maksymalny (całkowity) koszt łącza. Ten wariant algorytmu Dijkstry jest również znany jako algorytm Diala , na cześć Roberta B. Diala, który opublikował go w 1969 roku. Ten sam pomysł działa również, przy użyciu skwantyzowanej kolejki kubełków, dla grafów z dodatnimi wagami rzeczywistych krawędzi, gdy stosunek maksimum do minimalna waga wynosi co najwyżej c . W tej skwantyzowanej wersji algorytmu wierzchołki są przetwarzane poza kolejnością w porównaniu z wynikiem z nieskwantyzowaną kolejką priorytetową, ale nadal znajdowane są poprawne najkrótsze ścieżki. W tych algorytmach priorytety będą obejmować tylko zakres szerokości c + 1 , więc optymalizacja modułowa może zostać wykorzystana do zmniejszenia przestrzeni do O ( n + c ) .

problemu z najszerszą ścieżką można zastosować wariant tego samego algorytmu . W połączeniu z metodami szybkiego dzielenia niecałkowitych wag krawędzi na podzbiory, którym można przypisać priorytety liczb całkowitych, prowadzi to do prawie liniowych rozwiązań problemu z najszerszą ścieżką z jednym źródłem i jednym celem.

Chciwa okładka zestawu

Problem okładki zestawu ma na wejściu rodzinę zbiorów . Wynikiem powinna być podrodzina tych zestawów, z takim samym związkiem jak oryginalna rodzina, obejmująca jak najmniej zestawów. Jest NP-trudny , ale ma zachłanny algorytm aproksymacji , który osiąga logarytmiczny współczynnik aproksymacji, zasadniczo najlepszy z możliwych, chyba że P = NP . Ten algorytm aproksymacji wybiera swoją podrodzinę, wielokrotnie wybierając zestaw, który obejmuje maksymalną możliwą liczbę pozostałych odkrytych elementów. Standardowe ćwiczenie w projektowaniu algorytmów wymaga zaimplementowania tego algorytmu, który zajmuje czas liniowy w rozmiarze wejściowym, który jest sumą rozmiarów wszystkich zbiorów wejściowych.

Można to rozwiązać za pomocą kolejki zasobników zestawów w rodzinie wejściowej, uszeregowanych według liczby pozostałych elementów, które obejmują. Za każdym razem, gdy algorytm zachłanny wybiera zbiór jako część swojego wyniku, nowo objęte elementy zbioru należy odjąć od priorytetów innych zbiorów, które je obejmują; w trakcie algorytmu liczba tych zmian priorytetów jest po prostu sumą rozmiarów zbiorów wejściowych. Priorytety są monotonicznie malejącymi liczbami całkowitymi, których górna granica jest liczbą elementów do uwzględnienia. Każdy wybór algorytmu zachłannego polega na znalezieniu zestawu o maksymalnym priorytecie, co można zrobić, skanując w dół zasobniki kolejki zasobników, zaczynając od ostatniej poprzedniej wartości maksymalnej. Całkowity czas jest liniowy w rozmiarze wejściowym.

Planowanie

Kolejki kubełkowe mogą być wykorzystywane do planowania zadań z terminami, na przykład w przekazywaniu pakietów danych internetowych z gwarancją jakości usług . W przypadku tego zastosowania terminy powinny być skwantyzowane w dyskretnych przedziałach, a zadania, których terminy mieszczą się w tym samym przedziale, są uważane za mające równoważny priorytet.

Odmiana skwantyzowanej struktury danych kolejki zasobników, kolejka kalendarza , została zastosowana do planowania symulacji zdarzeń dyskretnych , w których elementy w kolejce to przyszłe zdarzenia, których priorytety są ustalane na podstawie czasu w symulacji, w którym zdarzenia powinny się wydarzyć. W tej aplikacji kolejność zdarzeń jest krytyczna, więc priorytetów nie można przybliżyć. W związku z tym kolejka kalendarza wyszukuje element o minimalnym priorytecie w inny sposób niż kolejka zasobników: w kolejce zasobników można zwrócić dowolny element pierwszego niepustego zasobnika, natomiast kolejka kalendarza przeszukuje wszystkie elementy w tego segmentu, aby określić, który z nich ma najmniejszy niekwantyzowany priorytet. Aby zapewnić szybkie wyszukiwanie, ta odmiana stara się zachować proporcjonalność liczby segmentów do liczby elementów, dostosowując skalę kwantyzacji i odbudowując strukturę danych, gdy traci ona równowagę. W najgorszym przypadku kolejki kalendarza mogą być wolniejsze niż kolejki zasobników (gdy wiele elementów ląduje w tym samym najmniejszym zasobniku), ale są szybkie, gdy elementy są równomiernie rozmieszczone w zasobnikach, co powoduje, że średni rozmiar zasobnika jest stały.

Szybki marsz

W matematyce stosowanej i metodach numerycznych do rozwiązywania równań różniczkowych nieporządne kolejki priorytetów były używane do ustalania priorytetów etapów metody szybkiego marszu do rozwiązywania problemów brzegowych równania Eikonala , używanego do modelowania propagacji fal . Ta metoda znajduje czasy, w których ruchoma granica przecina zestaw dyskretnych punktów (takich jak punkty siatki liczb całkowitych) przy użyciu metody ustalania priorytetów przypominającej ciągłą wersję algorytmu Dijkstry , a jej czas działania jest zdominowany przez kolejkę priorytetów z tych punktów. Można go przyspieszyć do czasu liniowego, zaokrąglając priorytety używane w tym algorytmie do liczb całkowitych i używając kolejki zasobników dla tych liczb całkowitych. Podobnie jak w algorytmach Dijkstry i Diala, priorytety są monotoniczne, więc w szybkim marszu można wykorzystać monotoniczną optymalizację kolejki zasobników i jej analizę. Jednak dyskretyzacja wprowadza pewien błąd do otrzymanych obliczeń.

Zobacz też

• Soft heap , inny sposób przyspieszania kolejek priorytetów za pomocą przybliżonych priorytetów