priority_queue — mereu cel mai prioritar primul

De ce contează?

Imaginează-ți triajul la urgență. Pacienții nu sunt tratați în ordinea sosirii, ci în ordinea gravității: cel mai urgent caz intră primul, chiar dacă a venit ultimul. Asistenta nu rearanjează toată sala — ține mereu „cel mai grav” la îndemână. Exact asta face o coadă cu priorități.

Ce este o coadă cu priorități?

O coadă cu priorități (priority queue) este o structură în care fiecare element are o prioritate, iar tu scoți mereu elementul cu prioritatea cea mai mare. Nu contează când l-ai adăugat — contează cât de „important” e.

În C++ ai priority_queue din <queue>. Implicit e un max-heap: vârful e mereu maximul. De ce e util? Pentru că ai nevoie repetat de „cel mai mare de acum”, fără să sortezi tot de fiecare dată.

Operațiile principale:

push — adaugă un element, O(log n);
top — citește elementul prioritar (maximul), O(1);
pop — scoate elementul prioritar, O(log n).

Cum funcționează, pas cu pas

Pornim cu coada goală și executăm: push 5, push 1, push 8, push 3.

push 5 → top = 5
push 1 → top = 5 (1 e mai mic, nu schimbă vârful)
push 8 → top = 8 (noul maxim urcă în vârf)
push 3 → top = 8

prioritate	8	5	3	1
	top

După cele 4 push-uri, top este 8 — maximul. Restul NU e complet sortat.

Acum scoatem pe rând cu pop, citind de fiecare dată top:

top = 8 → pop
top = 5 → pop
top = 3 → pop
top = 1 → pop

Ai obținut elementele în ordine descrescătoare, deși nu le-ai adăugat sortat.

Implementare C++

Întâi varianta implicită (max-heap), apoi min-heap-ul cu greater<int>:

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

int main() {
    // max-heap implicit: top() = maximul
    priority_queue<int> pq;
    pq.push(5);
    pq.push(1);
    pq.push(8);
    pq.push(3);

    cout << pq.top() << "\n";   // 8 (maximul)
    pq.pop();                   // scoate 8
    cout << pq.top() << "\n";   // 5
    cout << pq.size() << "\n";  // 3

    // min-heap: comparatorul greater face top() = minimul
    priority_queue<int, vector<int>, greater<int>> minHeap;
    minHeap.push(5);
    minHeap.push(1);
    minHeap.push(8);

    cout << minHeap.top() << "\n";  // 1 (minimul)
    return 0;
}

Reține tiparul de citire: top() arată vârful, apoi pop() îl scoate. La fel ca la stivă, pop() nu întoarce valoarea — o citești cu top() înainte.

Unde o folosești

Dijkstra — extragi mereu nodul cu distanța minimă; aici se folosește un min-heap.
K cele mai mari elemente dintr-un șir — ții un heap de dimensiune k.
Heap sort sau orice problemă de tip „dă-mi mereu extremul curent”.

Complexitate

Operație	Timp	Spațiu
push	O(log n)	—
pop	O(log n)	—
top	O(1)	—
size / empty	O(1)	—
total structură	—	O(n)

Observația-cheie

priority_queue se bazează intern pe un heap binar stocat într-un vector. De aceea garantează doar că vârful e extremul — restul elementelor sunt „parțial” ordonate, doar cât e nevoie pentru a menține proprietatea de heap.

Greșeli frecvente

Greșeli frecvente de concurs:

Crezi că structura e complet sortată: NU. Doar top() e garantat extremul. Dacă vrei toate elementele în ordine, le scoți pe rând cu pop.
Uiți greater<int> la min-heap: fără el rămâne max-heap și iei maximul când voiai minimul.
top() / pop() pe coadă goală: comportament nedefinit. Verifică mereu !pq.empty() înainte.
Aștepți ca pop() să întoarcă valoarea: nu o întoarce. Citește cu top(), apoi pop().

Vizualizare

Urmărește cum noul maxim „urcă” spre vârf la fiecare push și cum se reașază heap-ul după pop:

Indiciu

Folosește ← / → pentru a vedea pas cu pas cum se reface proprietatea de heap. Observă că un push afectează doar un drum de la frunză spre rădăcină — de aici cei O(log n).

Recapitulare

priority_queue e implicit max-heap: top() întoarce mereu maximul, în O(1).
Min-heap: priority_queue<int, vector<int>, greater<int>> — citește în cod, nu memora pe dinafară.
push/pop sunt O(log n), structura nu e complet sortată, iar pe baza ei stă un heap binar.