Kolejka priorytetowa
Kolejka priorytetowa (ang. priority queue) – abstrakcyjny typ danych służący do reprezentowania zbioru elementów, z których każdy ma przyporządkowaną wartość zwaną kluczem[1].
Zastosowania
edytujKolejka priorytetowa jest abstrakcyjnym typem danych. Istnieją różne implementacje tej idei, różniące się czasem działania, kosztem i innymi cechami.
Operacje
edytujKolejki typu max
edytujNa kolejkach tego typu można wykonywać następujące operacje[1] (niech S oznacza zbiór):
| Nazwa | Opis |
|---|---|
| insert(S, x) | Wstawianie nowego elementu x do zbioru. Matematycznie: |
| maximum(S) | Zwrócenie elementu o największym kluczu. |
| extract_max(S) | Zwrócenie elementu o największym kluczu z jednoczesnym usunięciem go ze zbioru. |
| increase_key(S, x, k) | Zwiększa wartość klucza elementu x na nową wartość k przy założeniu, że jest on nie mniejszy, niż aktualna wartość klucza. |
Kolejki priorytetowe typu max są używane m.in. do szeregowania procesów w jądrach systemów operacyjnych[1][3].
Kolejki typu min
edytujNa kolejkach tego typu można wykonywać następujące operacje[1] (niech S oznacza zbiór):
| Nazwa | Opis |
|---|---|
| insert(S, x) | Wstawianie nowego elementu x do zbioru. Matematycznie: |
| minimum(S) | Zwrócenie elementu o najmniejszym kluczu. |
| extract_min(S) | Zwrócenie elementu o najmniejszym kluczu z jednoczesnym usunięciem go ze zbioru. |
| decrease_key(S, x, k) | Zmienia wartość klucza elementu x na nową wartość k przy założeniu, że jest ona nie większa, niż aktualna wartość klucza. |
Kolejki priorytetowe tego typu są używane m.in. w symulatorach zdarzeń[1].
Przy założeniu, że dane są b-bitowymi liczbami całkowitymi, a pamięć komputera składa się z adresowalnych słów b-bitowych, można zaimplementować operację minimum działającą w czasie stałym, a operacje insert oraz extract-min w działające w czasie [4]. Przy założeniu, że pamięć jest nieograniczona (lub przy założeniu pamięci liniowej przy użyciu randomizowanego haszowania) można uzyskać oszacowanie [5].
Przypisy
edytuj- ↑ a b c d e f g Thomas H. Cormen i inni, Wprowadzenie do algorytmów, Krzysztof Diks (tłum.) i inni, wyd. VII (I w PWN), Warszawa: PWN, 2015, ISBN 978-83-01-16911-4 (pol.).
- ↑ a b Kolejki priorytetowe [online], users.uj.edu.pl [dostęp 2016-08-19] [zarchiwizowane z adresu 2016-09-01].
- ↑ Jędrzej Ułasiewicz, Sieciowe systemy operacyjne, szeregowanie [online] [dostęp 2017-12-27] [zarchiwizowane z adresu 2016-04-29].
- ↑ Michael Fredman, Dan Willard, Surpassing the information theoretic boundwith fusion trees, „Journal of Computer and System Sciences”, 47(3), grudzień 1993, s. 424–436 (ang.).
- ↑ Mikkel Thorup, On RAM priority queues, „SIAM Journal of Computing”, 30(1), 2000, s. 86–109 (ang.).