Kolejka priorytetowa () – 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): NazwaOpisinsert(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.
Kolejki typu min Na kolejkach tego typu można wykonywać następujące operacje (niech S oznacza zbiór): NazwaOpisinsert(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ń.
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 . 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 .
Przypisy
Kategoria:Struktury danych