`std::priority_queue` în C++

Adaptoare: stack, queue, priority_queue C++98

Coadă cu priorități: top() returnează mereu elementul cel mai mare (sau cel mai mic, cu std::greater).

Sintaxă

#include <queue>

std::priority_queue<T> nume;                                     // cel mai mare în vârf
std::priority_queue<T, std::vector<T>, std::greater<T>> nume;    // cel mai mic în vârf
const T& top() const;

Ce face `std::priority_queue`

std::priority_queue ține elementele astfel încât cel mai „important” să fie mereu în vârf. Implicit, acesta este cel mai mare (după <). push și pop durează O(log n), top() O(1). În spate este un heap într-un std::vector.

Pentru cel mai mic element în vârf (de exemplu în algoritmul lui Dijkstra), scrie tipul complet: std::priority_queue<int, std::vector<int>, std::greater<int>>. Pentru perechi, compararea se face întâi după first, apoi după second.

Doar vârful este accesibil; restul elementelor nu sunt sortate și nu pot fi parcurse.

Parametri

Parametru	Descriere
`T`	Tipul elementelor.
`Comparator`	Opțional: `std::greater<T>` pentru minim în vârf, sau un comparator propriu.

Ce returnează

top(): referință constantă la elementul cu prioritate maximă.

Exemple

Exemplul 1: Cel mai mare și cel mai mic în vârf

#include <functional>
#include <print>
#include <queue>
#include <vector>

int main() {
    std::priority_queue<int> maxim;
    std::priority_queue<int, std::vector<int>, std::greater<int>> minim;
    for (int x : {5, 1, 8, 3, 9, 2}) {
        maxim.push(x);
        minim.push(x);
    }
    std::print("max-heap: ");
    while (!maxim.empty()) {
        std::print("{} ", maxim.top());
        maxim.pop();
    }
    std::print("\nmin-heap: ");
    while (!minim.empty()) {
        std::print("{} ", minim.top());
        minim.pop();
    }
    std::println();
}

Rezultat

max-heap: 9 8 5 3 2 1 
min-heap: 1 2 3 5 8 9

Exemplul 2: Sarcini cu priorități

Perechile se compară întâi după prioritate (first); la egalitate, după text (second), deci la aceeași prioritate iese întâi textul mai mare alfabetic.

#include <print>
#include <queue>
#include <string>
#include <utility>

int main() {
    std::priority_queue<std::pair<int, std::string>> sarcini;
    sarcini.emplace(2, "răspuns la e-mailuri");
    sarcini.emplace(5, "repară serverul");
    sarcini.emplace(1, "comandă cafea");
    sarcini.emplace(5, "backup baza de date");

    while (!sarcini.empty()) {
        const auto& [prioritate, ce] = sarcini.top();
        std::println("[{}] {}", prioritate, ce);
        sarcini.pop();
    }
}