Baza wiedzyCentrum egzaminacyjne
PLPolski
Wybierz język13

CKTIS / C++

std::priority_queue — kolejka priorytetowa

std::priority_queue udostępnia element o najwyższym priorytecie, a nie najwcześniej dodany. Domyślnie na szczycie znajduje się największa wartość; std::greater<T> odwraca kolejność.

Wersja: C++23; repository compiler flag, production runtime not attested

Składnia

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

std::priority_queue<T> q;
std::priority_queue<T, std::vector<T>, std::greater<T>> min_q;

std::priority_queue z nagłówka <queue> to adapter kontenera utrzymujący kopiec, nie kolejkę FIFO. Domyślnie używa std::vector<T> i porównania std::less<T>, więc top() wskazuje największą wartość. Wariant z std::greater<T> wskazuje najmniejszą; wymaga nagłówka <functional>.

push() dodaje wartość, a emplace() konstruuje element w kontenerze i przywraca własność kopca. top() daje dostęp tylko do odczytu. pop() usuwa szczyt i zwraca void: potrzebną wartość skopiuj przed usunięciem. Przed top() i pop() sprawdź empty(); obie operacje wymagają niepustej kolejki.

Komparator musi definiować ścisły słaby porządek. Compare(a, b) == true oznacza, że a poprzedza b w tym porządku, czyli ma niższy priorytet przy pobieraniu. Adapter nie udostępnia iteratorów ani operacji zmiany priorytetu dowolnego elementu.

top() ma stały koszt. Naprawa kopca podczas push(), emplace() i pop() wymaga O(log n) porównań. Dodawanie obejmuje również koszt kontenera: realokacja domyślnego std::vector<T> może uczynić pojedyncze wstawienie liniowym.

Przykład wypisuje te same dane malejąco i rosnąco, opróżniając obie kolejki. Zakres wpisu to C++23; podlinkowany roboczy projekt standardu jest nowszy i nie jest zamrożonym tekstem C++23.

Przykłady

#include <functional>
#include <iostream>
#include <queue>
#include <vector>

int main() {
    std::priority_queue<int> max_q;
    std::priority_queue<int, std::vector<int>, std::greater<int>> min_q;

    for (int value : {4, 1, 7, 1}) {
        max_q.push(value);
        min_q.push(value);
    }

    while (!max_q.empty()) {
        std::cout << max_q.top();
        max_q.pop();
        std::cout << (max_q.empty() ? '\n' : ' ');
    }
    while (!min_q.empty()) {
        std::cout << min_q.top();
        min_q.pop();
        std::cout << (min_q.empty() ? '\n' : ' ');
    }
}

Wynik

7 4 1 1
1 1 4 7

Wyświetlony kod i zadeklarowany wynik zweryfikowano w odizolowanym środowisku metodą zapisaną w dowodzie weryfikacji tej dokładnej wersji.

Źródła