Base de conhecimentoCentro de Exames
PT · PTPortuguês (Portugal)
Escolher idioma13

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.

Fontes