Struktury danych/Kolejki/Kolejka priorytetowa

Spis treści
Wstęp	Wstęp - Konwencje
Struktury danych	Podstawy - Tablice - Listy - Stosy - Kolejki - Drzewa - Zbiory - Kopce - Find-Union - Tablice z haszowaniem - Grafy
Dodatki	Złożoność obliczeniowa - Implementacje w C++ - Implementacje w Pascalu - Bibliografia - Dla twórców podręcznika

Kolejka priorytetowa

Kolejka priorytetowa jest kolejnym przykładem abstrakcyjnego typu danych, jest w gruncie rzeczy bardzo podobna do stosu czy kolejki omawianych wcześniej. Tak samo jak one jest strukturą liniową, główną różnicą jest to, że każdy element ma dodatkowo przypisany priorytet. Ze względu na wartość priorytetu elementy są potem szeregowane jak w normalnej kolejce. Im wyższy priorytet tym szybciej zostanie dany element „ściągnięty” z kolejki. W przypadku, gdy jakieś elementy mają ten sam priorytet są usuwane jak w kolejce FIFO.

Zastosowanie kolejki priorytetowej można bardzo łatwo odszukać w każdym systemie operacyjnym. Weźmy dowolny wielowątkowy system operacyjny i załóżmy, że pewien wykonywany proces będzie chciał skorzystać z danych znajdujących się na dysku. Zanim będzie mógł je odczytać powinien zwolnić procesor dla jakiegoś innego procesu, ponieważ odczyt z dysku jest nieporównywalnie wolniejszy od dostępu do danych w rejestrach. W czasie, w którym czekałby na dane procesor mógłby wykonać naprawdę wiele cykli, od razu widać zasadność wywłaszczenia. Tylko teraz skąd system ma wziąć inny proces, który by mógł wykonywać swój kod na procesorze? Z pomocą przychodzi kolejka gotowych procesów, które właśnie w tej strukturze czekają aż zostanie im przydzielony ten zasób. Można porównać to do zakorkowanej drogi oraz pojazdu uprzywilejowanego, który potrzebuje przejechać szybciej niż wszystkie inne pojazdy, bo na przykład jest to ambulans, który spieszy się do kogoś po wypadku samochodowym. Od razu widać, że takie operację są naturalne na kolejce priorytetowej.

Nasza implementacja kolejki priorytetowej będzie wykorzystywała kopiec, należy jednak pamiętać, że w zamyśle jest to zupełnie inna od niego struktura. Podobnie jak lista, którą można implementować za pomocą tablicy lub listy wiązanej.

W kontekście LIFO i FIFO

Bardzo łatwo jest myśleć o kolejce priorytetowej jak o modyfikacji standardowej kolejki. Jednak przyjrzyjmy się temu problemowi nieco dokładniej. Przypomnijmy sobie stos ( kolejność LIFO ) oraz kolejkę ( kolejność FIFO), biorąc pod uwagę sposób w jaki usuwamy z nich elementy tak na prawdę mamy do czynienia z kolejką priorytetową o bardzo specyficznym systemie nadawania ważności elementom. W stosie priorytet każdego dołożonego elementu monotonicznie rośnie,dlatego element dołożony ostatnio jest zawsze ściągany pierwszy. Natomiast w kolejce priorytet monotonicznie maleje, co powoduje, że element dodany jako pierwszy jest usuwany jako pierwszy.

Implementacja

Zakładamy, że nasza kolejka będzie najpierw przepuszczać elementy o wyższym priorytecie ( nic nie stoi na przeszkodzie, żeby działała na odwrót ). Do tego celu wykorzystamy kopiec typu max. Zalecamy najpierw zapoznać się z rozdziałem o kopcach zanim przystąpisz do dalszej lektury.

Kolejka priorytetowa typu max

• INSERT(S:kolejka, d:Data) - analogicznie do poprzednich dodaje element d do zbioru S.
• MAXIMUM(S:kolejka)
• EXRTACT-MAX(S:kolejka) – usuwa i w wyniku zwraca element o największym kluczu
• INCREASE-KEY(S:kolejka, d:Data, k:integer) – zmienia wartość klucza elementu d na liczbę k, zakładamy, że k jest nie mniejsze od od obecnej wartości klucza.