O que é a estrutura de dados priority_queue?

priority_queue — um adaptador de contêiner da biblioteca padrão C++ que fornece funcionalidade de fila de prioridade. Os elementos são extraídos em ordem de prioridade (por padrão, o elemento de maior valor tem a maior prioridade). É, na essência, uma camada sobre outro contêiner (por padrão std::vector) que usa algoritmos de heap (std::make_heap, std::push_heap, std::pop_heap) para manter a estrutura de heap dentro do contêiner base.

Características principais:

• Prioridade: Os elementos são extraídos de acordo com sua prioridade. Por padrão, usa-se std::less para determinar a prioridade, o que significa que o elemento maior é considerado de maior prioridade (heap máximo). Pode-se alterar a ordem fornecendo outro comparador, por exemplo, std::greater para um heap mínimo.
• Adaptador: priority_queue não é um contêiner independente, mas adapta outro contêiner base (geralmente std::vector, mas pode ser outro, como std::deque), fornecendo uma interface de fila de prioridade.
• Heap: Implementado internamente usando um heap, garantindo complexidade logarítmica para operações de inserção e extração.
• Acesso não ordenado: Não fornece acesso arbitrário aos elementos. Apenas as operações de inserção (push), remoção do elemento de maior prioridade (pop) e visualização do elemento de maior prioridade (top) estão disponíveis.

Operações principais:

Operação	Descrição	Complexidade (média/peor caso)
push	Insere um elemento com prioridade dada.	O(log N)
pop	Remove o elemento de maior prioridade.	O(log N)
top	Retorna uma referência constante ao elemento de maior prioridade.	O(1)
empty	Verifica se a fila está vazia.	O(1)
size	Obtém o número de elementos na fila.	O(1)

Exemplo de uso:

#include <queue>
#include <vector>
#include <iostream>
#include <functional> // para std::greater

int main() {
    // Heap máximo (padrão)
    std::priority_queue<int> max_pq;
    max_pq.push(10);
    max_pq.push(30);
    max_pq.push(20);

    std::cout << "Elementos do heap máximo (top): ";
    while (!max_pq.empty()) {
        std::cout << max_pq.top() << " ";
        max_pq.pop();
    }
    std::cout << std::endl;

    // Heap mínimo (usando std::greater<int>)
    std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq;
    min_pq.push(10);
    min_pq.push(30);
    min_pq.push(20);

    std::cout << "Elementos do heap mínimo (top): ";
    while (!min_pq.empty()) {
        std::cout << min_pq.top() << " ";
        min_pq.pop();
    }
    std::cout << std::endl;

    return 0;
}