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. Cormen i inni, Wprowadzenie do algorytmów, Krzysztof Diks (tłum.) 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ędrzej Ułasiewicz, Sieciowe systemy operacyjne, szeregowanie.
  4. Michael Fredman, Dan Willard, Surpassing the information theoretic boundwith fusion trees, „Journal of Computer and System Sciences”, 47(3), grudzień 1993, s. 424-436 (ang.).
  5. Mikkel Thorup, On RAM priority queues, „SIAM Journal of Computing”, 30(1), 2000, s. 86-109 (ang.).