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
Kolejka priorytetowa jest abstrakcyjnym typem danych. Istnieją różne implementacje tej idei, różniące się czasem działania, kosztem i innymi cechami.
Operacje
Kolejki typu max
Na 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
Na 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
- ↑ a b c d e f g Thomas H.T.H. Cormen Thomas H.T.H. i inni, Wprowadzenie do algorytmów, KrzysztofK. 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ędrzejJ. Ułasiewicz JędrzejJ., Sieciowe systemy operacyjne, szeregowanie [online] [dostęp 2017-12-27] [zarchiwizowane z adresu 2016-04-29] .
- ↑ MichaelM. Fredman MichaelM., DanD. Willard DanD., Surpassing the information theoretic boundwith fusion trees, „Journal of Computer and System Sciences”, 47(3), grudzień 1993, s. 424–436 (ang.).
- ↑ MikkelM. Thorup MikkelM., On RAM priority queues, „SIAM Journal of Computing”, 30(1), 2000, s. 86–109 (ang.).