Kolejka priorytetowa

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

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

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

Kolejki typu max[edytuj | edytuj kod]

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

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

  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 978-83-01-16911-4 (pol.).
  2. a b Kolejki priorytetowe, users.uj.edu.pl [dostęp 2016-08-19].
  3. Jędrzej Ułasiewicz, Sieciowe systemy operacyjne, szeregowanie [dostęp 2017-12-27].
  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.).