Qu'est-ce que la structure de données priority_queue…

priority_queue — un adaptador de contenedor de la biblioteca estándar de C++ que proporciona funcionalidad de cola de prioridad. Los elementos se extraen en orden de prioridad (por defecto, el elemento más grande tiene la mayor prioridad). Es, en esencia, un envoltorio sobre otro contenedor (por defecto std::vector) que utiliza algoritmos de montículo (std::make_heap, std::push_heap, std::pop_heap) para mantener la estructura de montículo dentro del contenedor base.

Características clave:

Prioridad: Los elementos se extraen según su prioridad. Por defecto, se usa std::less para determinar la prioridad, lo que significa que el elemento más grande se considera de mayor prioridad (montículo máximo). Se puede cambiar el orden proporcionando otro comparador, por ejemplo, std::greater para un montículo mínimo.
Adaptador: priority_queue no es un contenedor independiente, sino que adapta otro contenedor base (generalmente std::vector, pero puede ser otro, como std::deque), proporcionando una interfaz de cola de prioridad.
Montículo: Internamente implementado usando un montículo, lo que garantiza una complejidad logarítmica para las operaciones de inserción y extracción.
Acceso no ordenado: No proporciona acceso arbitrario a los elementos. Solo están disponibles las operaciones de inserción (push), extracción del elemento con mayor prioridad (pop) y vista del elemento con mayor prioridad (top).

Operaciones principales:

Operación	Descripción	Complejidad (promedio/peor caso)
`push`	Inserta un elemento con prioridad dada.	O(log N)
`pop`	Elimina el elemento con mayor prioridad.	O(log N)
`top`	Devuelve una referencia constante al elemento con mayor prioridad.	O(1)
`empty`	Verifica si la cola está vacía.	O(1)
`size`	Obtiene el número de elementos en la cola.	O(1)

Ejemplo de uso:

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

int main() {
    // Montículo máximo (por defecto)
    std::priority_queue<int> max_pq;
    max_pq.push(10);
    max_pq.push(30);
    max_pq.push(20);

    std::cout << "Elementos del montículo máximo (top): ";
    while (!max_pq.empty()) {
        std::cout << max_pq.top() << " ";
        max_pq.pop();
    }
    std::cout << std::endl;

    // Montículo 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 del montículo mínimo (top): ";
    while (!min_pq.empty()) {
        std::cout << min_pq.top() << " ";
        min_pq.pop();
    }
    std::cout << std::endl;

    return 0;
}

Utilisé dans des algorithmes où il est nécessaire d'extraire constamment l'élément avec la priorité la plus élevée (ou la plus basse), comme l'algorithme de Dijkstra, l'algorithme de Prim ou dans des tâches de modélisation d'événements.

Qu'est-ce que la structure de données priority_queue ?