Clase de contenedor C++<priority_queue>

En C++,<priority_queue>es parte de la biblioteca de plantillas estándar (STL) y se utiliza para implementar una cola de prioridad.

Una cola de prioridad es una cola especial que permite acceder rápidamente al elemento de mayor (o menor) prioridad de la cola.

En C++,priority_queuepor defecto es un montículo máximo, lo que significa que el elemento superior de la cola siempre tiene el valor más grande.

priority_queuees un adaptador de contenedor que proporciona operaciones de montículo sobre el contenedor subyacente. No proporciona iteradores ni admite acceso aleatorio.

Sintaxis

A continuación se muestrapriority_queuela sintaxis básica de:

#include <queue>

// 声明一个整型优先队列
priority_queue<int> pq;

// 声明一个自定义类型的优先队列，需要提供比较函数
struct compare {
    bool operator()(int a, int b) {
        return a > b; // 这里定义了最小堆
    }
};
priority_queue<int, vector<int>, compare> pq_min;

Operaciones comunes

  • empty(): comprobar si la cola está vacía.
  • size(): devolver el número de elementos de la cola.
  • top(): devolver el elemento superior de la cola (sin eliminarlo).
  • push(): agregar un elemento a la cola.
  • pop(): eliminar el elemento superior de la cola.

Ejemplo

A continuación se muestrapriority_queueun ejemplo sencillo: crearemos un montículo máximo y mostraremos cómo agregar elementos y obtener el elemento superior de la cola.

Ejemplo

#include <iostream>
#include <queue>

int main() {
    // Crear una cola de prioridad de enteros
    std::priority_queue<int> pq;

    // Agregar elementos a la cola de prioridad
    pq.push(30);
    pq.push(10);
    pq.push(50);
    pq.push(20);

    // Mostrar los elementos de la cola
    std::cout << "Elementos en la cola:" << std::endl;
    while (!pq.empty()) {
        std::cout << pq.top() << std::endl;
        pq.pop();
    }

    return 0;
}

Resultado de salida:

队列中的元素：
50
30
20
10

Prioridad personalizada

Si necesitas un montículo mínimo, puedes lograrlo definiendo una función de comparación personalizada:

Ejemplo

#include <iostream>
#include <queue>
#include <vector>

struct compare {
    bool operator()(int a, int b) {
        return a > b; // Definir un montículo mínimo
    }
};

int main() {
    // Crear una cola de prioridad de tipo personalizado usando un montículo mínimo
    std::priority_queue<int, std::vector<int>, compare> pq_min;

    // Agregar elementos a la cola de prioridad
    pq_min.push(30);
    pq_min.push(10);
    pq_min.push(50);
    pq_min.push(20);

    // Mostrar los elementos de la cola
    std::cout << "Elementos en el montículo mínimo:" << std::endl;
    while (!pq_min.empty()) {
        std::cout << pq_min.top() << std::endl;
        pq_min.pop();
    }

    return 0;
}

Resultado de salida:

最小堆中的元素：
10
20
30
50

<priority_queue>es un contenedor muy útil en el STL de C++, especialmente adecuado para escenarios donde se necesita acceder rápidamente al elemento de mayor o menor prioridad. Mediante una función de comparación personalizada, podemos implementar fácilmente un montículo máximo o mínimo. Espero que este artículo ayude a los principiantes a comprender y utilizar mejorpriority_queue。

Otras extensiones