Kolejka priorytetowa

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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[edytuj]

Kolejka priorytetowa jest abstrakcyjnym typem danych. Istnieją różne implementacje tej idei, różniące się czasem, działania, kosztem i innymi cechami.

Operacje[edytuj]

Kolejki typu max[edytuj]

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[edytuj]

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) Zwiększa wartość klucza elementu x na nową wartość k przy założeniu, że jest on nie większy, 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

  1. a b c d e f g Thomas H.T.H. Cormen Thomas H.T.H., Charles E.Ch.E. Leiserson Charles E.Ch.E., Ronald L.R.L. Rivest Ronald L.R.L., CliffordC. Stein CliffordC. i inni, Wprowadzenie do algorytmów, KrzysztofK. Diks (tłum.), AdamA. Malinowski (tłum.), DariaD. Roszkowska (tłum.), WojciechW. Rytter (tłum.), AgnieszkaA. Łydżba, EwaE. Zdanowicz (red.) i inni, wyd. VII (I w PWN), Warszawa: PWN, 2015, ISBN 9788301169114 (pol.).
  2. a b Kolejki priorytetowe, users.uj.edu.pl [dostęp 2016-08-19].
  3. JędrzejJ. Ułasiewicz JędrzejJ., Sieciowe systemy operacyjne, szeregowanie.
  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.).