Red sa prioritetom (priority_queue) u C++

Lekcija 8 od 11 · Strukture podataka

Red sa prioritetom uvek daje element sa najvećim (ili najmanjim) prioritetom, a dodavanje i uzimanje traju samo O(log n). Koristi se u Dijkstrinom algoritmu, za izbor „sledećeg najboljeg“ i u mnogim pohlepnim algoritmima.

Pre nego što počneš: potrebno predznanje – Red (queue), Stek.
Kako da učiš: svaki primer prekucaj i pokreni, a zadatke na kraju prvo reši sam/a; uputstvo i rešenje otvori tek posle toga. Svi programi su u C++-u.

Osnovne operacije

Operacija	Značenje	Složenost
`pq.push(x)`	dodaje element	O(log n)
`pq.top()`	vraća element sa najvećim prioritetom (ne uklanja ga)	O(1)
`pq.pop()`	uklanja taj element	O(log n)
`pq.size()`, `pq.empty()`	broj elemenata, da li je prazan	O(1)

Unutra je hip (heap) – drvo u kome je svaki roditelj veći od svoje dece, pa je najveći element uvek u korenu. Zaglavlje je <queue>.

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    priority_queue<int> maks;                               // podrazumevano: najveći na vrhu
    priority_queue<int, vector<int>, greater<int>> mini;    // najmanji na vrhu
    for (int x : {5, 1, 8, 3}) {
        maks.push(x);
        mini.push(x);
    }
    while (!maks.empty()) { cout << maks.top() << " "; maks.pop(); }
    cout << "\n";
    while (!mini.empty()) { cout << mini.top() << " "; mini.pop(); }
    cout << "\n";
    return 0;
}

Parovi i sopstveni prioritet

Ako su u redu parovi pair<int,int>, porede se prvo po prvom, pa po drugom elementu. Uobičajen trik: u prvi element stavi prioritet, a u drugi podatak (npr. čvor grafa). Za min-hip parova piše se priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<>> – baš tako izgleda red u Dijkstrinom algoritmu.

Za složeniji kriterijum piše se struktura sa operatorom poređenja; pazi da je logika „obrnuta“: element za koji poređenje vraća true ide niže.

Tipične primene

k najvećih elemenata toka podataka – min-hip veličine k;
spajanje uvek dva najmanja elementa (užad, Hafmanovo kodiranje);
raspored poslova – uvek uzmi posao sa najvećim prioritetom ili najranijim rokom;
najkraći putevi – Dijkstra, Prim (Primov algoritam).

Zadaci za vežbu

Za svaki zadatak postoji primer, uputstvo i rešenje. Rešenja su provereno tačna na primerima iz teksta.

ZADATAK 01Težina: Srednje teško

k najvećih brojeva

Učitava se n brojeva (n ≤ 10⁶) i broj k. Ispiši k najvećih, od najvećeg ka manjem, koristeći memoriju samo za k brojeva.

Primer

Ulaz

7 3
5 1 9 3 7 9 2

Izlaz

9 9 7

Rešenje (C++)

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    priority_queue<int, vector<int>, greater<int>> pq;    // min-hip
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        pq.push(x);
        if ((int)pq.size() > k) pq.pop();                 // izbaci najmanji
    }
    vector<int> rez;
    while (!pq.empty()) { rez.push_back(pq.top()); pq.pop(); }
    reverse(rez.begin(), rez.end());                      // od najvećeg
    for (int i = 0; i < (int)rez.size(); i++) cout << rez[i] << (i + 1 < (int)rez.size() ? " " : "\n");
    return 0;
}

ZADATAK 02Težina: Srednje teško

Spajanje užadi

Imamo n komada užeta datih dužina. Spajanje dva komada dužina a i b košta a + b i daje komad dužine a + b. Koliko najmanje košta spajanje svih komada u jedan?

Primer

Ulaz

4
4 3 2 6

Izlaz

Rešenje (C++)

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    priority_queue<long long, vector<long long>, greater<long long>> pq;
    for (int i = 0; i < n; i++) {
        long long x;
        cin >> x;
        pq.push(x);
    }
    long long cena = 0;
    while (pq.size() > 1) {
        long long a = pq.top(); pq.pop();
        long long b = pq.top(); pq.pop();
        cena += a + b;
        pq.push(a + b);          // novi komad ide nazad u red
    }
    cout << cena << endl;
    return 0;
}

ZADATAK 03Težina: Teže

Poslovi sa prioritetom

Poslovi stižu tokom vremena: posao i stiže u trenutku t[i], traje d[i] i ima prioritet p[i]. Procesor radi jedan po jedan posao do kraja; kad je slobodan, od pristiglih bira onaj sa najvećim prioritetom (za isti prioritet – onaj koji je ranije stigao). Ispiši redosled izvršavanja (redni brojevi od 1).

Primer

Ulaz

Izlaz

1 2 4 3

Rešenje (C++)

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> t(n), d(n), p(n);
    vector<int> red(n);
    for (int i = 0; i < n; i++) { cin >> t[i] >> d[i] >> p[i]; red[i] = i; }
    sort(red.begin(), red.end(), [&](int a, int b) { return t[a] < t[b] || (t[a] == t[b] && a < b); });

    priority_queue<pair<long long, int>> pq;      // (prioritet, -indeks): veći prioritet, pa manji indeks
    long long vreme = 0;
    int j = 0;
    vector<int> izvrseno;
    while ((int)izvrseno.size() < n) {
        while (j < n && t[red[j]] <= vreme) {     // svi poslovi koji su do sada stigli
            pq.push({p[red[j]], -red[j]});
            j++;
        }
        if (pq.empty()) {                          // procesor čeka sledeći posao
            vreme = t[red[j]];
            continue;
        }
        int i = -pq.top().second;
        pq.pop();
        izvrseno.push_back(i + 1);
        vreme += d[i];
    }
    for (int i = 0; i < n; i++) cout << izvrseno[i] << (i + 1 < n ? " " : "\n");
    return 0;
}

Česte greške i saveti

Podrazumevani priority_queue je max-hip; za najmanji element na vrhu dodaj vector<T>, greater<T>.
top() na praznom redu je greška – uvek prvo proveri empty().
U redu ne može da se menja prioritet postojećeg elementa; umesto toga ubaci novi par, a zastareli preskoči kad izađe (tako radi Dijkstra).
Ako ti treba i najmanji i najveći, ili brisanje proizvoljnog elementa, koristi multiset.

Proveri znanje

Otvori kviz

Mini kviz: red sa prioritetom

1. Koji element vraća top() kod priority_queue<int>?

najmanji
najveći
prvi dodat

2. Kolika je složenost operacije push?

O(1)
O(log n)
O(n)

3. Koji red treba za Dijkstrin algoritam?

max-hip po rastojanju
min-hip po rastojanju
običan red (queue)

Red sa prioritetom (priority_queue) u C++

Osnovne operacije

Parovi i sopstveni prioritet

Tipične primene

Zadaci za vežbu

k najvećih brojeva

Primer

Ulaz

Izlaz

Uputstvo

Rešenje (C++)

Spajanje užadi

Primer

Ulaz

Izlaz

Uputstvo

Rešenje (C++)

Poslovi sa prioritetom

Primer

Ulaz

Izlaz

Uputstvo

Rešenje (C++)

Proveri znanje

Mini kviz: red sa prioritetom