22. Kolejki priorytetowe i metody ich realizacji.
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 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.
Najczęściej kolejkę priorytetową realizuje się za pomocą kopca lub tablicy asocjacyjnej.
Tablica asocjacyjna - przechowuje pary (unikalny klucz, wartość) i umożliwia dostęp do wartości poprzez podanie klucza. W przypadku kolejek, tablica mapuje wartość priorytetu na listę wartości z tym priorytetem.
Kopiec (sterta, ang. heap, tłumaczone też jako stóg lub sterta) - struktura danych oparta na drzewie, w której wartości potomków węzła są w stałej relacji z wartością rodzica.
Kopce mogą być używane do implementacji kolejek priorytetowych, ponieważ ustalenie odpowiedniej relacji umożliwia bezpośredni dostęp do wierzchołka o największej/najmniejszej wartości z danego zbioru zapisanego w kopcu.
Widać, że kolejność wstawiania danych przyjmuje charakterystyczny porządek. Do istniejących węzłów dołączane są maksymalnie po dwa nowe, aż do ulokowania wszystkich w stercie. Cechą charakterystyczną sterty jest to, że wartość każdego węzła jest większa od wartości węzłów jego dwóch potomków, jeśli takowe istnieją. Sposób organizacji drzewa ułatwia operacje wstawiania i usuwania elementów. Można bowiem nowy element bez problemu dopisać na koniec tablicy (co zaburzy istniejący porządek), a następnie za pomocą prostych modyfikacji przywrócić tablicy (drzewu) własności sterty.
Implementacja kolejki priorytetowej przy użyciu kopca charakteryzuje się bardzo szybkim (O(1)) dostępem do elementu maksymalnego.