Kolejka priorytetowa

W C++ mamy również strukturę danych o nazwie kolejka priorytetowa. Kolejka priorytetowa zapewnia specjalną funkcjonalność, której nie ma zwykła kolejka: każdemu elementowi przypisana jest wartość priorytetu, a elementy są obsługiwane na podstawie tego priorytetu.

Podstawowa kolejka priorytetowa jest skonstruowana tak, że jej pierwszy element jest największy ze wszystkich, a pozostałe są posortowane w kolejności malejącej.

priority_queue<dataType> queueName

Najpierw musimy dołączyć plik nagłówkowy kolejki priorytetowej na początku naszego pliku C++. 

Tworzymy kolejkę priorytetową tak jak pozostałe poznane już kontenery.

priority_queue<int> integers;

Następnie używamy metody push(), aby dodać nowe elementy do kolejki. Element zostaje dodany, a jeśli jest większy od wszystkich pozostałych, będzie przechowywany jako pierwszy. Jeśli jest mniejszy od wszystkich pozostałych elementów, będzie przechowywany jako ostatni i tak dalej.

integers.push(5);  // integers = {5)

Do wyświetlania elementów używamy metody top(), tak jak w przypadku stosu. Wyświetla ona element o najwyższym priorytecie; w przypadku liczb całkowitych będzie to największa liczba.

integers.push(100);  // integers = {100, 5}
integers.push(10);  // integers = {100, 10, 5}
integers.push(3);  // integers = {100, 10, 5, 3}
cout << integers.top();

Output:
100

Elementy usuwamy również tak jak ze stosu, za pomocą metody pop(). Usuwa ona element ze szczytu, czyli element o najwyższym priorytecie. W przypadku liczb jest to największa z nich.

integers.pop();  // integers = {10, 5, 3}
cout << integers.top();

Output:
10

Możemy zmienić priorytet kolejki, według którego sortowane są elementy. Możemy na przykład zadeklarować kolejkę priorytetową, która sortuje liczby całkowite w kolejności rosnącej, jak poniżej:

priority_queue<int, vector<int>, greater<int> > integers;

W tej kolejce wstawiane elementy są sortowane w kolejności rosnącej. Gdy zechcemy wyświetlić element ze szczytu lub usunąć go za pomocą metody pop(), zostanie wyświetlona lub usunięta najmniejsza liczba.

Na razie nie przejmuj się używaniem kolejki priorytetowej w inny sposób ani zmianą priorytetu. Pamiętaj tylko, że ta struktura danych jest dostępna do naszego użytku, więc możemy sortować elementy według pewnego rodzaju priorytetu

Metody kolejki priorytetowej