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: ${\displaystyle 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: ${\displaystyle 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 ${\displaystyle \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 ${\displaystyle \mathrm {O} (\log _{2}{\log _{2}{n}})}$^[5].

Przypisy