Dydaktyka‎ > ‎Notatki‎ > ‎

Kolejka priorytetowa

opublikowane: 26 sty 2011, 06:06 przez Rafał Nowak   [ zaktualizowane 3 mar 2016, 00:36 przez Rafał Nowak ]
Obiecałem dzisiaj klasie Ia, że napiszę trochę o kolejce priorytetowej. Otóż mówiliśmy na lekcji, że jest ona dziwnym tworem, nazwaliśmy go WORKIEM, do którego można wrzucać liczby i wyjmować w kolejności zgodnej z ich priorytetem.

W STL-u, tj. po wpisaniu na samym początku tego
#include<queue>
możemy korzystać z kolejki w następujący sposób
priority_queue<int> Q; // deklaracja kolejki priorytetowej Q

Q.push( 10 ); // wrzuca do kolejki liczbę 10
x = Q.top();  // podstawia pod x wartość liczby w kolejce Q z największym priorytetem
Q.pop();      // usuwa z kolejki Q liczbę z największym priorytetem
Domyślnie największy priorytet mają liczby największe, tzn. jeśli wykonamy
Q.push(20);
Q.push(30);
Q.push(4);

x = Q.top();
to wartość zmiennej x będzie wynosiła 30.

Jeśli chcemy, aby największy priorytet miały liczby o najmniejszej wartości, to zgodnie z tym, co pisałem już kiedyś na moim blogu [tutaj], musimy zadeklarować kolejkę w następujący sposób:
// deklaracja kolejki priorytetowej Q, w której element top()
// ma najmniejszą wartość
priority_queue<int, vector<int>, greater<int> > Q;
Przykładowe programy można znaleźć na mojej RNO-Wiki [tutaj], a szczegółową dokumentację techniczną na stronie autorów biblioteki STL - tutaj.
Comments