Informatyka MIMUW

Kolejka priorytetowa to jedna z podstawowych abstrakcyjnych struktur danych, wykorzystywana między innymi w takich zastosowaniach jak:

• algorytm Dijkstry wyznaczania najkrótszych ścieżek w grafach;
• algorytm Prima znajdowania minimalnego drzewa rozpinającego;
• symulacja sterowana zdarzeniami;
• metoda zamiatania w geometrii obliczeniowej;
• kodowanie Huffmana;
• sortowanie (algorytm Heapsort).

Oferuje ona następujące operacje:

• MakePQ(): tworzy nową, pustą kolejkę;
• Insert(H,x): wstawia element x (o kluczu z pewnego liniowo uporządkowanego uniwersum) do kolejki H;
• FindMin(H): zwraca element o najmniejszym kluczu w kolejce H;
• DelMin(H): zwraca element o najmniejszym kluczu w kolejce H, usuwając go przy tym z H.

Ten zestaw operacji często rozszerza się o:

• DecreaseKey(H,x,y): nadaje kluczowi elementu x w kolejce H nową, mniejszą wartość y;
• Delete(H,x): usuwa element x z kolejki H.

Jeśli struktura danych udostępnia dodatkowo operację łączenia kolejek

• Meld(H1,H2): zwraca nową kolejkę, zawierającą wszystkie elementy z kolejek H1 i H2, niszcząc je przy tym;

to nazywamy ją złączalną kolejką priorytetową.

Najprostszą, choć niezbyt efektywną implementację kolejki priorytetowej stanowi zwykła lista. Znacznie efektywniejszy jest kopiec binarny (wykorzystywany w algorytmie HeapSort), nie pozwala on jednak na szybkie łączenie kolejek. Przedstawione na tym wykładzie struktury danych: kopiec dwumianowy i kopiec Fibonacciego, umożliwiają efektywne wykonywanie wszystkich operacji złączalnej kolejki priorytetowej.
Oto tabela kosztów poszczególnych operacji w wymienionych implementacjach, przy założeniu, że w kolejce(ach) jest aktualnie \( n \) elementów:

Uwaga: wyszukiwanie elementu nie należy do zestawu operacji (złączalnej) kolejki priorytetowej, dlatego w przypadku operacji DecreaseKey i Delete zakładamy, że jako parametr przekazywane jest dowiązanie do elementu, którego ma dotyczyć operacja.