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.

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
• Tablice
• Kopce i sterty
• Drzewa

Operacje

Kolejki typu max

Na kolejkach tego typu można wykonywać następujące operacje (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.

Kolejki typu min

Na kolejkach tego typu można wykonywać następujące operacje (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ń.

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}}})$. 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}})$.