Wolisz obejrzeć?
Olimpijskie Koło Informatyczne nagrywa swoje zajęcia i udostępnia je za darmo. Poniżej 2 odcinki o tym temacie — dobre uzupełnienie, jeśli wolisz obejrzeć niż przeczytać.
Po co komu kolejka z pierwszeństwem
Wyobraź sobie szpitalny oddział ratunkowy. Ludzie przychodzą w dowolnej kolejności, ale jako pierwszy trafia do lekarza nie ten, kto czeka najdłużej, tylko ten w najgorszym stanie. To właśnie robi priority_queue: przyjmuje elementy w dowolnej kolejności, a wydaje zawsze ten najważniejszy.
Domyślnie „najważniejszy” znaczy największy. Dodajesz liczby jak popadnie, a na wierzchu zawsze leży największa z nich — bez żadnego sortowania z Twojej strony.
// wektor: po kazdym dodaniu trzeba szukac
vector<int> v;
v.push_back(5);
v.push_back(9);
v.push_back(3);
// szukanie najwiekszego za kazdym razem
int maks = v[0];
for (int x : v) maks = max(maks, x);
cout << maks;
#include <queue>
priority_queue<int> pq;
pq.push(5);
pq.push(9);
pq.push(3);
// najwiekszy zawsze pod reka
cout << pq.top();
priority_queue<int> pq;
Pusty kopiec liczb. Nagłówek: #include <queue>.
pq.push(x)
Wrzuca x do środka. Kolejność wrzucania nie ma żadnego znaczenia.
pq.top()
Podgląda największy element — nie usuwa go.
pq.pop()
Usuwa największy. Nic nie zwraca — najpierw top(), potem pop().
pq.size()
Ile elementów jest w środku.
pq.empty()
Zawsze sprawdzaj przed top(). Zajrzenie do pustego kopca wysypuje program.
#include <iostream>
#include <queue>
using namespace std;
int main() {
priority_queue<int> pq;
pq.push(5);
pq.push(9);
pq.push(1);
pq.push(7);
// wyjmujemy po kolei - zawsze najwiekszy
while (!pq.empty()) {
cout << pq.top() << " "; // podejrzyj
pq.pop(); // usun
}
return 0;
}
Zwróć uwagę na parę top i pop. W C++ te dwie rzeczy są rozdzielone: top() tylko pokazuje, pop() tylko usuwa i nic nie zwraca. Dlatego zawsze robisz je po kolei — najpierw zapamiętujesz wartość, potem usuwasz.
Gdy najważniejszy ma być najmniejszy
Domyślny kopiec wydaje największy element. Czasem potrzebujesz odwrotnie — na przykład gdy szukasz najtańszej opcji albo najkrótszego czasu. Wtedy tworzysz kopiec minimum, dopisując do deklaracji dwie rzeczy.
// domyslnie: najwiekszy na wierzchu
priority_queue<int> pq;
pq.push(5);
pq.push(9);
pq.push(1);
while (!pq.empty()) {
cout << pq.top() << " ";
pq.pop();
}
// najmniejszy na wierzchu
priority_queue<int,
vector<int>,
greater<int>> pq;
pq.push(5);
pq.push(9);
pq.push(1);
while (!pq.empty()) {
cout << pq.top() << " ";
pq.pop();
}
Deklaracja kopca minimum jest brzydka i długa — nikt jej nie pamięta, wszyscy ją kopiują. Zapisz ją sobie gdzieś albo wracaj po nią na tę stronę. Środkowy vector<int> to techniczny szczegół, którego nie musisz rozumieć; ważne jest tylko słowo greater na końcu.
Jest też prostsza sztuczka, jeśli nie chcesz zapamiętywać tej deklaracji: wrzucaj liczby ze znakiem minus. Największa z liczb ujemnych to najmniejsza z oryginalnych — wystarczy przy wyjmowaniu odwrócić znak z powrotem.
#include <iostream>
#include <queue>
using namespace std;
int main() {
priority_queue<int> pq; // zwykly kopiec max
// wrzucamy z minusem
pq.push(-5);
pq.push(-9);
pq.push(-1);
// i odwracamy przy wyjmowaniu
while (!pq.empty()) {
cout << -pq.top() << " ";
pq.pop();
}
return 0;
}
Pary, struktury i typowe zastosowania
Kopiec par działa tak samo jak sortowanie par: decyduje pierwsze pole, a przy remisie drugie. Dzięki temu naturalnie modeluje sytuację „rzecz z przypisaną ważnością” — na wierzchu ląduje ta o najwyższym priorytecie.
#include <queue>
#include <string>
// {priorytet, opis}
priority_queue<pair<int, string>> sor;
sor.push({2, "zlamana reka"});
sor.push({9, "zawal"});
sor.push({4, "wysoka goraczka"});
while (!sor.empty()) {
auto [waga, opis] = sor.top();
cout << waga << " - " << opis << "\n";
sor.pop();
}
#include <queue>
// znajdz 3 najwieksze liczby
priority_queue<int> pq;
int x;
while (cin >> x) pq.push(x);
for (int i = 0; i < 3 && !pq.empty(); i++) {
cout << pq.top() << " ";
pq.pop();
}
Kiedy kopiec wygrywa z posortowaniem? Wtedy, gdy dane napływają na bieżąco albo gdy potrzebujesz tylko kilku największych. Sortowanie wymaga wszystkich danych naraz; kopiec przyjmuje je po jednym i w każdej chwili wie, co jest na wierzchu.
Klasyczny przykład: łączysz liny, płacąc za każde połączenie sumę długości. Żeby zapłacić jak najmniej, trzeba za każdym razem łączyć dwie najkrótsze — a kopiec minimum podaje je natychmiast, nawet gdy po każdym połączeniu wrzucasz do niego nową linę.
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
// kopiec minimum - najkrotsza na wierzchu
priority_queue<int, vector<int>, greater<int>> pq;
for (int i = 0; i < n; i++) {
int dlugosc;
cin >> dlugosc;
pq.push(dlugosc);
}
int koszt = 0;
while (pq.size() > 1) {
int a = pq.top(); pq.pop();
int b = pq.top(); pq.pop();
koszt += a + b;
pq.push(a + b); // nowa lina wraca do kopca
}
cout << koszt;
return 0;
}
I najważniejsze ograniczenie: kopiec nie pozwala przeglądać zawartości. Widzisz wyłącznie wierzchołek. Nie ma pq[i], nie da się przejść go pętlą ani sprawdzić, czy coś w środku jest. Gdy potrzebujesz takich rzeczy — sięgnij po set albo posortowany vector.
Wszystko, co robi się z kopcem
Kopiec ma dosłownie pięć operacji. Cała trudność polega na zapamiętaniu, że top i pop to dwie osobne rzeczy.
| Zapis | Co robi | Uwaga |
|---|---|---|
priority_queue<int> pq; |
Kopiec maksimum — największy na wierzchu. | Nagłówek <queue> |
priority_queue<int, vector<int>, greater<int>> pq; |
Kopiec minimum — najmniejszy na wierzchu. | Skopiuj, nie zapamiętuj |
pq.push(x) |
Wrzuca element. | Kolejność wrzucania bez znaczenia |
pq.top() |
Podgląda wierzchołek. | Nie usuwa |
pq.pop() |
Usuwa wierzchołek. | Nic nie zwraca |
pq.size() |
Liczbę elementów. | — |
pq.empty() |
Czy kopiec jest pusty. | Sprawdzaj przed top() |
priority_queue<pair<int,int>> |
Kopiec par — decyduje pierwsze pole. | Rzecz z priorytetem |
pq.push(-x) |
Sztuczka na kopiec minimum. | Przy wyjmowaniu odwróć znak |
Wiersze czwarty i piąty to najczęstsze potknięcie. W C++ top() i pop() są rozdzielone: pierwsze pokazuje, drugie usuwa i nic nie oddaje. Zapis int x = pq.pop(); nie skompiluje się.
Sprawdź się na zadaniach
Sześć zadań od najprostszego. W każdym kluczem jest pytanie: czy potrzebuję całości posortowanej, czy tylko tego, co aktualnie najważniejsze? Najpierw spróbuj sam.
n liczb, wrzuć je do kopca i wypisz wszystkie od największej do najmniejszej.while (!pq.empty()), a w środku top() i pop() — w tej kolejności.Pokaż rozwiązanie
#include <iostream>
#include <queue>
using namespace std;
int main() {
int n;
cin >> n;
priority_queue<int> pq;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
pq.push(x);
}
while (!pq.empty()) {
cout << pq.top() << " ";
pq.pop();
}
return 0;
}
greater<int>, albo sztuczka z minusem: wrzucaj -x, a przy wyjmowaniu wypisuj -pq.top().Pokaż rozwiązanie
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
priority_queue<int, vector<int>, greater<int>> pq;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
pq.push(x);
}
while (!pq.empty()) {
cout << pq.top() << " ";
pq.pop();
}
return 0;
}
k największych (wartość k podana jest jako pierwsza).k razy. Pamiętaj o zabezpieczeniu !pq.empty() na wypadek, gdyby liczb było mniej niż k.Pokaż rozwiązanie
#include <iostream>
#include <queue>
using namespace std;
int main() {
int k;
cin >> k;
priority_queue<int> pq;
int x;
while (cin >> x) pq.push(x);
for (int i = 0; i < k && !pq.empty(); i++) {
cout << pq.top() << " ";
pq.pop();
}
return 0;
}
n pacjentów: nazwisko i stopień pilności (im wyższy, tym pilniej). Wypisz kolejność, w jakiej trafią do lekarza. Przy równej pilności decyduje kolejność alfabetyczna nazwiska.{pilnosc, nazwisko} ustawi pacjentów po pilności sam. Ale uwaga: przy remisie kopiec wyda nazwisko późniejsze alfabetycznie, bo wydaje zawsze największe. Odwróć to, wrzucając nazwisko w parze jako drugie pole i korzystając z kopca minimum na parze {-pilnosc, nazwisko}.Pokaż rozwiązanie
#include <iostream>
#include <queue>
#include <vector>
#include <string>
using namespace std;
int main() {
int n;
cin >> n;
// kopiec minimum na {-pilnosc, nazwisko}
priority_queue<pair<int, string>,
vector<pair<int, string>>,
greater<pair<int, string>>> pq;
for (int i = 0; i < n; i++) {
string nazwisko;
int pilnosc;
cin >> nazwisko >> pilnosc;
pq.push({-pilnosc, nazwisko});
}
while (!pq.empty()) {
auto [p, nazwisko] = pq.top();
pq.pop();
cout << nazwisko << " (" << -p << ")\n";
}
return 0;
}
n lin o podanych długościach. Połączenie dwóch lin kosztuje tyle, ile wynosi suma ich długości, a w wyniku powstaje jedna dłuższa lina. Połącz wszystkie w jedną, płacąc jak najmniej.Pokaż rozwiązanie
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
priority_queue<int, vector<int>, greater<int>> pq;
for (int i = 0; i < n; i++) {
int d;
cin >> d;
pq.push(d);
}
long long koszt = 0;
while (pq.size() > 1) {
int a = pq.top(); pq.pop();
int b = pq.top(); pq.pop();
koszt += a + b;
pq.push(a + b);
}
cout << koszt;
return 0;
}
Pokaż rozwiązanie
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() {
priority_queue<int> dol; // mniejsza polowa
priority_queue<int, vector<int>, greater<int>> gora; // wieksza polowa
int x;
while (cin >> x) {
// wrzucamy do wlasciwego kopca
if (dol.empty() || x <= dol.top()) dol.push(x);
else gora.push(x);
// wyrownujemy rozmiary
if (dol.size() > gora.size() + 1) {
gora.push(dol.top()); dol.pop();
} else if (gora.size() > dol.size()) {
dol.push(gora.top()); gora.pop();
}
cout << dol.top() << "\n";
}
return 0;
}
Częste błędy i dobre praktyki
priority_queue<int> wydaje największy element. Na najmniejszy potrzebujesz wariantu z greater albo sztuczki z minusem.int x = pq.top();, dopiero potem pq.pop();. Zapis int x = pq.pop(); to błąd kompilacji.top() na pustym kopcu wysypuje program, i to bez czytelnego komunikatu. Pętla zawsze z while (!pq.empty()).pq[i] ani pętli po elementach. Widzisz wyłącznie wierzchołek — to cena za szybkość.priority_queue<int, vector<int>, greater<int>> — nikt tego nie pamięta. Zapisz sobie w notatkach.while (!pq.empty()) zostawia pusty kopiec. Jeśli dane są potrzebne później, zapisz je najpierw do wektora.