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.