CKTIS / C++
std::priority_queue — fila de prioridade
std::priority_queue disponibiliza o elemento com maior prioridade, não o que foi inserido primeiro. Por predefinição, o maior valor fica no topo; std::greater<T> inverte a ordem.
Versão: C++23; repository compiler flag, production runtime not attested
Sintaxe
#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 de <queue> é um adaptador de contentor que mantém um heap, não uma fila FIFO. Por predefinição, usa std::vector<T> e std::less<T>, pelo que top() identifica o maior valor. A variante que usa std::greater<T> identifica o menor e requer <functional>.
push() insere um valor, enquanto emplace() constrói um elemento no contentor e restabelece a propriedade de heap. top() proporciona acesso só de leitura. pop() remove o elemento do topo e devolve void: copie os valores necessários antes de os remover. Verifique empty() antes de top() e pop(); ambas as operações exigem uma fila não vazia.
O comparador tem de definir uma ordenação fraca estrita. Compare(a, b) == true significa que a precede b nessa ordenação e, por isso, tem menor prioridade de extração. O adaptador não disponibiliza iteradores nem uma operação para alterar a prioridade de um elemento arbitrário.
top() tem custo constante. A reparação do heap durante push(), emplace() e pop() requer O(log n) comparações. A inserção inclui também o custo do contentor subjacente: a realocação do std::vector<T> predefinido pode tornar uma inserção individual linear.
O exemplo apresenta os mesmos dados por ordem decrescente e crescente, esvaziando ambas as filas. Esta entrada destina-se a C++23; o projeto de trabalho associado é mais recente e não é um texto C++23 congelado.
Exemplos
#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' : ' ');
}
}
Resultado
7 4 1 1 1 1 4 7
O código apresentado e o resultado declarado foram verificados num ambiente isolado pelo método registado na prova de verificação desta versão exata.