Base de conocimientosCentro de exámenes
ESEspañol
Elegir idioma13

CKTIS / C++

std::priority_queue — cola de prioridad

std::priority_queue ofrece el elemento de mayor prioridad, no el que se insertó primero. De forma predeterminada, el valor más grande queda arriba; std::greater<T> invierte el orden.

Versión: C++23; repository compiler flag, production runtime not attested

Sintaxis

#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> es un adaptador de contenedor que mantiene un montículo, no una cola FIFO. De forma predeterminada usa std::vector<T> y std::less<T>, por lo que top() señala el valor más grande. La variante con std::greater<T> señala el más pequeño y requiere <functional>.

push() inserta un valor, mientras que emplace() construye un elemento en el contenedor y restablece la propiedad de montículo. top() proporciona acceso de solo lectura. pop() elimina el elemento superior y devuelve void: copia antes cualquier valor que necesites. Comprueba empty() antes de top() y pop(); ambas operaciones requieren que la cola no esté vacía.

El comparador debe definir un orden débil estricto. Compare(a, b) == true significa que a precede a b en ese orden y, por tanto, tiene menor prioridad de extracción. El adaptador no proporciona iteradores ni una operación para cambiar la prioridad de un elemento arbitrario.

top() tiene coste constante. La reparación del montículo durante push(), emplace() y pop() requiere O(log n) comparaciones. La inserción también incluye el coste del contenedor subyacente: la reasignación del std::vector<T> predeterminado puede hacer que una inserción individual sea lineal.

El ejemplo imprime los mismos datos en orden descendente y ascendente y vacía ambas colas. Esta entrada tiene como objetivo C++23; el borrador de trabajo enlazado es más reciente y no es un texto de C++23 congelado.

Ejemplos

#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

El código mostrado y el resultado declarado se verificaron en un entorno aislado mediante el método registrado en la evidencia de verificación de esta versión exacta.

Fuentes