licencjat - opracowania (wszystkie


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.



Wyszukiwarka

Podobne podstrony:
licencjat - opracowania (wszystkie
licencjat - opracowania (wszystkie
licencjat - opracowania (wszystkie
licencjat - opracowania (wszystkie
licencjat - opracowania (wszystkie
licencjat - opracowania (wszystkie
licencjat - opracowania (wszystkie
licencjat - opracowania (wszystkie
licencjat - opracowania (wszystkie
licencjat - opracowania (wszystkie
licencjat - opracowania (wszystkie
licencjat - opracowania (wszystkie
licencjat - opracowania (wszystkie

więcej podobnych podstron