C++ · Kontenery · priority_queue

Kopiec, czyli kolejka z pierwszeństwem

Kolejka, w której pierwszy obsługiwany jest nie ten, kto przyszedł najwcześniej, tylko ten najważniejszy. Dokładnie jak na szpitalnym oddziale ratunkowym.

Filmy z OKI

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ć.

Materiały Olimpijskiego Koła Informatycznego — kanał zewnętrzny. Kliknięcie odtwarza film tutaj, bez opuszczania strony.

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.

recznie.cpp
// 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;
▶ Wyjście programu
9
kopcem.cpp
#include <queue>

priority_queue<int> pq;

pq.push(5);
pq.push(9);
pq.push(3);

// najwiekszy zawsze pod reka
cout << pq.top();
▶ Wyjście programu
9
📦

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.

podstawy.cpp
#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;
}
▶ Wyjście programu
9 7 5 1

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.

kopiec_max.cpp
// 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();
}
▶ Wyjście programu
9 5 1
kopiec_min.cpp
// 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();
}
▶ Wyjście programu
1 5 9

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.

minus_trik.cpp
#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;
}
▶ Wyjście programu
1 5 9

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.

pary.cpp
#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();
}
▶ Wyjście programu
9 - zawal 4 - wysoka goraczka 2 - zlamana reka
k_najwiekszych.cpp
#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();
}
▶ Wyjście programu
Wejście: 4 15 8 23 16 23 16 15

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ę.

liny.cpp
#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;
}
▶ Wyjście programu
Wejście: 4 4 3 2 6 29

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.

ZapisCo robiUwaga
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.

Łatwe Największy na wierzchu
Wczytaj n liczb, wrzuć je do kopca i wypisz wszystkie od największej do najmniejszej.
Jak to ugryźć: Zadanie na rozgrzewkę. Pętla while (!pq.empty()), a w środku top() i pop() — w tej kolejności.
Pokaż rozwiązanie
kopiec_max.cpp
#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;
}
Łatwe Od najmniejszej
To samo co poprzednio, ale wypisz liczby rosnąco — używając kopca minimum.
Jak to ugryźć: Albo pełna deklaracja z greater<int>, albo sztuczka z minusem: wrzucaj -x, a przy wyjmowaniu wypisuj -pq.top().
Pokaż rozwiązanie
kopiec_min.cpp
#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;
}
Łatwe K największych liczb
Wczytuj liczby aż do końca danych, a potem wypisz k największych (wartość k podana jest jako pierwsza).
Jak to ugryźć: Wrzuć wszystko do kopca maksimum, a potem wyjmij dokładnie k razy. Pamiętaj o zabezpieczeniu !pq.empty() na wypadek, gdyby liczb było mniej niż k.
Pokaż rozwiązanie
k_najwiekszych.cpp
#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;
}
Średnie Kolejka na SOR
Wczytaj 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.
Jak to ugryźć: Kopiec par {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
sor.cpp
#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;
}
Średnie Łączenie lin
Masz 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.
Jak to ugryźć: Za każdym razem łącz dwie najkrótsze — wtedy najdłuższe liny doliczane są najrzadziej. Kopiec minimum podaje je natychmiast, a nowo powstałą linę wrzucasz z powrotem do kopca.
Pokaż rozwiązanie
liny.cpp
#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;
}
Trudne Mediana na bieżąco
Wczytuj liczby jedna po drugiej i po każdej wypisz medianę wszystkich wczytanych do tej pory.
Jak to ugryźć: Sortowanie po każdej nowej liczbie byłoby za wolne. Sztuczka: trzymaj dwa kopce — maksimum na mniejszą połowę i minimum na większą. Mediana to wtedy wierzchołek większego z nich. Po każdym wstawieniu wyrównuj rozmiary, przerzucając element między kopcami.
Pokaż rozwiązanie
mediana.cpp
#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

⬆️
Domyślnie największy
Zwykły priority_queue<int> wydaje największy element. Na najmniejszy potrzebujesz wariantu z greater albo sztuczki z minusem.
✋
pop() nic nie zwraca
Najpierw int x = pq.top();, dopiero potem pq.pop();. Zapis int x = pq.pop(); to błąd kompilacji.
⚠️
Sprawdzaj empty()
Wywołanie top() na pustym kopcu wysypuje program, i to bez czytelnego komunikatu. Pętla zawsze z while (!pq.empty()).
🚫
Brak przeglądania
Nie ma pq[i] ani pętli po elementach. Widzisz wyłącznie wierzchołek — to cena za szybkość.
📋
Skopiuj deklarację kopca min
priority_queue<int, vector<int>, greater<int>> — nikt tego nie pamięta. Zapisz sobie w notatkach.
🔄
Wyjmowanie opróżnia kopiec
Przejście pętlą while (!pq.empty()) zostawia pusty kopiec. Jeśli dane są potrzebne później, zapisz je najpierw do wektora.

Gotowy na więcej?

Dołącz do T-Olimpians i trenuj z doświadczonymi mentorami. Zbuduj bazę, która prowadzi do finałów OI.