Programare Competitivă

deque și priority_queue din STL

deque<T> - coadă cu două capete

#include <deque>
using namespace std;

deque<int> dq;

dq.push_back(3);    // adaugă la spate: [3]
dq.push_back(7);    // [3, 7]
dq.push_front(1);   // adaugă în față: [1, 3, 7]

cout << dq.front(); // 1
cout << dq.back();  // 7
cout << dq[1];      // 3 (acces prin indice)

dq.pop_front();     // scoate din față: [3, 7]
dq.pop_back();      // scoate din spate: [3]

cout << dq.size();  // 1

Operații

Operație Ce face Complexitate
push_back(x) Adaugă la spate O(1)
push_front(x) Adaugă în față O(1)
pop_back() Scoate din spate O(1)
pop_front() Scoate din față O(1)
front() Primul element O(1)
back() Ultimul element O(1)
dq[i] Acces prin indice O(1)
size() Număr elemente O(1)
empty() Verifică gol O(1)

Exemplu: minim pe fereastră glisantă

#include <fstream>
#include <deque>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int v[100001];
int n, k;

int main()
{
    fin >> n >> k;
    for (int i = 1; i <= n; i++)
        fin >> v[i];

    deque<int> dq; // stocăm indici

    for (int i = 1; i <= n; i++) {
        while (!dq.empty() && dq.front() < i - k + 1)
            dq.pop_front();

        while (!dq.empty() && v[dq.back()] >= v[i])
            dq.pop_back();

        dq.push_back(i);

        if (i >= k)
            fout << v[dq.front()] << " ";
    }

    return 0;
}

Identic cu implementarea manuală, dar mai curat.

priority_queue<T> - coadă de priorități

priority_queue este un max-heap implicit: elementul cel mai mare e mereu în vârf.

#include <queue> // priority_queue e tot în <queue>
using namespace std;

priority_queue<int> pq;

pq.push(3);
pq.push(7);
pq.push(2);
pq.push(9);

cout << pq.top();  // 9 (maximul)

pq.pop();          // scoate 9
cout << pq.top();  // 7

cout << pq.size(); // 3

Operații

Operație Ce face Complexitate
push(x) Inserează element O(log n)
pop() Scoate maximul O(log n)
top() Returnează maximul O(1)
size() Număr elemente O(1)
empty() Verifică gol O(1)

Min-heap cu priority_queue

Implicit e max-heap. Pentru min-heap, folosim greater<int>:

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

pq.push(3);
pq.push(7);
pq.push(2);

cout << pq.top();  // 2 (minimul!)

Declarația e mai lungă dar funcționează identic, doar că vârful e minimul.

Truc rapid: dacă nu vrei să memorezi declarația pentru min-heap, poți insera valorile negate: push -x în max-heap, și top va fi -max = min. La extragere, negăm înapoi.

Exemplu: cele mai mici K elemente

#include <fstream>
#include <queue>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int main()
{
    int n, k;
    fin >> n >> k;

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

    for (int i = 1; i <= n; i++) {
        int x;
        fin >> x;
        pq.push(x);
    }

    for (int i = 1; i <= k; i++) {
        fout << pq.top() << " ";
        pq.pop();
    }

    return 0;
}

date.in:

8 3
5 3 8 1 9 2 7 4

date.out:

1 2 3

Priority queue cu pair

Putem stoca perechi. Sortarea e după .first, apoi .second:

priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;

pq.push({5, 1});  // (cost, nod)
pq.push({2, 3});
pq.push({7, 2});

cout << pq.top().first << " " << pq.top().second; // 2 3 (minimul după cost)

Aceasta e baza algoritmului Dijkstra pentru drumuri minime în grafuri.

Exemplu: interclasarea a K vectori sortați

Avem K vectori sortați, vrem să îi combinăm într-unul singur, sortat. Folosim un min-heap cu perechea (valoare, indexul vectorului).

#include <fstream>
#include <queue>
#include <vector>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int main()
{
    int k;
    fin >> k;

    vector<vector<int>> vecs(k);
    vector<int> poz(k, 0); // poziția curentă în fiecare vector

    for (int i = 0; i < k; i++) {
        int n;
        fin >> n;
        vecs[i].resize(n);
        for (int j = 0; j < n; j++)
            fin >> vecs[i][j];
    }

    // Min-heap: (valoare, index_vector)
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;

    // Inserăm primul element din fiecare vector
    for (int i = 0; i < k; i++)
        if (!vecs[i].empty())
            pq.push({vecs[i][0], i});

    while (!pq.empty()) {
        int val = pq.top().first;
        int idx = pq.top().second;
        pq.pop();

        fout << val << " ";

        poz[idx]++;
        if (poz[idx] < (int)vecs[idx].size())
            pq.push({vecs[idx][poz[idx]], idx});
    }

    return 0;
}

Comparație

stack queue deque priority_queue
Adaugă vârf spate ambele auto-sortat
Scoate vârf față ambele max/min
Acces top front ambele + indice top
Ordine LIFO FIFO ambele Heap

Greșeli frecvente

1. priority_queue e max-heap implicit

priority_queue<int> pq;
pq.push(1); pq.push(5); pq.push(3);
cout << pq.top(); // 5, NU 1!

Pentru min-heap: priority_queue<int, vector<int>, greater<int>>.

2. pop() nu returnează valoare

La toate structurile STL, pop() returnează void. Citim cu top() / front() înainte.

3. Include greșit

priority_queue și queue sunt ambele în <queue>. deque e în <deque>.

Ce să reții

  • deque<T>: push/pop la ambele capete + acces prin indice. Ideal pentru fereastră glisantă.
  • priority_queue<T>: max-heap implicit. Cu greater<T> devine min-heap.
  • priority_queue cu pair e baza lui Dijkstra.
  • pop() nu returnează valoare la nicio structură STL.
Cuprins Inapoi Inainte