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.

Listy^[2]
Tablice^[2]
Kopce i sterty^[1]
Drzewa^[1]

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: $S:=S\cup {\{x\}}$
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: $S:=S\cup {\{x\}}$
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 $\mathrm {O} ({\sqrt {\log _{2}{n}}})$ ^[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 $\mathrm {O} (\log _{2}{\log _{2}{n}})$ ^[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.).

[:0-1] ↑ ^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.).

[:1-2] Kolejki priorytetowe [online], users.uj.edu.pl [dostęp 2016-08-19] [zarchiwizowane z adresu 2016-09-01] .

[3] JędrzejJ. Ułasiewicz JędrzejJ., Sieciowe systemy operacyjne, szeregowanie [online] [dostęp 2017-12-27] [zarchiwizowane z adresu 2016-04-29] .

[4] 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.).

[5] MikkelM. Thorup MikkelM., On RAM priority queues, „SIAM Journal of Computing”, 30(1), 2000, s. 86–109 (ang.).

[1]

[2]

[3]

[4]

[5]