Kolejka priorytetowa
Z Wikipedii
Kolejka priorytetowa (ang. priority queue) – struktura danych służąca do przechowywania elementów zbioru, na którym określono relację porządku. Kolejka priorytetowa charakteryzuje się bardzo szybkim (O(1)) dostępem do elementu maksymalnego. Najczęściej kolejkę priorytetową realizuje się za pomocą kopca.
Kolejka priorytetowa ma zastosowanie tam, gdzie obiekty są pobierane z dynamicznej struktury i przetwarzane w kolejności od obiektu o najwyższym priorytecie do obiektu o najniższym priorytecie. Przy czym, w trakcie procesu przetwarzania nowe obiekty mogą być dodawane do kolejki.
Złożoność podstawowych operacji:
- wstawienie elementu: O(lg(n)),
- dostęp do maksymalnego elementu: O(1),
- usunięcie maksymalnego elementu: O(lg(n)),
- dostęp/usunięcie dowolnego elementu: O(n).
Zobacz też: kopiec
