De ce contează?
La urgenta dintr-un spital, pacientii nu sunt tratati in ordinea sosirii. Cineva
cu o fractura grava intra inaintea cuiva venit mai devreme cu o raceala. La
fiecare pas, medicul ia mereu cazul cel mai urgent, oricand ar fi ajuns acela.
Asta face un priority_queue: iti da mereu elementul cu cea mai mare prioritate,
nu pe primul intrat.
Ce este
Un priority_queue (coada cu prioritate) este o structura care iti da acces
rapid la cel mai mare element curent. Spre deosebire de o coada obisnuita,
unde iese primul cel care a intrat primul (FIFO), aici iese mereu maximul,
indiferent de ordinea in care l-ai adaugat.
Trei operatii o definesc:
push(x)— adaugi un element. CostaO(log n).top()— citesti maximul curent, fara sa-l scoti. CostaO(1).pop()— scoti maximul curent. CostaO(log n).
In spate sta un heap (un arbore binar tinut compact intr-un vector), de unde si numele vizualizatorului de mai jos. Tu nu trebuie sa-l implementezi — STL o face pentru tine.
Implicit, priority_queue<int> este un max-heap: top este maximul. Daca
vrei ca top sa fie minimul, ceri un min-heap cu un comparator:
priority_queue<int, vector<int>, greater<int>>. E singura schimbare necesara —
restul operatiilor raman identice.