C++ Priority Queue con comparador personalizado

Una cola de prioridad (o priority queue en inglés) es una estructura de datos importante en programación que nos permite mantener un conjunto de elementos y acceder al elemento con la mayor (o menor) prioridad en todo momento. En C++, la cola de prioridad se implementa mediante la plantilla de clase priority_queue en la biblioteca estándar de STL.

Sin embargo, en ciertos escenarios puede ser necesario establecer un orden personalizado para los elementos en la cola de prioridad. Por ejemplo, es posible que queramos ordenar objetos según uno de sus atributos en lugar de su orden natural. Por suerte, el priority_queue de C++ nos permite especificar un comparador personalizado para definir el orden de los elementos.

En este artículo, aprenderás cómo implementar una cola de prioridad en C++ con un comparador personalizado.

Definición de cola de prioridad con comparador personalizado

Para definir una cola de prioridad con un comparador personalizado, necesitamos conocer la sintaxis de priority_queue:

priority_queue

- Tipo de dato: el tipo de elemento en la cola de prioridad.
- Contenedor: el contenedor subyacente utilizado para almacenar los elementos en la cola de prioridad. Podemos especificar un contenedor predeterminado, como vector o deque, o cualquier otro contenedor que implemente las operaciones básicas de acceso y eliminación en el extremo posterior.
- Comparador: una clase o función que define el orden personalizado de los elementos en la cola de prioridad.

La siguiente es una definición de plantilla general para una cola de prioridad con un comparador personalizado:

priority_queue , Comparador> pq;

Ejemplo de comparador personalizado

Para definir un comparador personalizado, tenemos que implementar un operador de llamada que tome dos elementos y devuelva verdadero si el primer elemento tiene mayor prioridad que el segundo, o falso de lo contrario. El siguiente es un ejemplo de comparador personalizado para una cola de prioridad de pares de enteros, donde el primer elemento del par tiene mayor prioridad:

struct myComparator{
    bool operator() (pair p1, pair p2){
        return p1.first < p2.first;
    }
};

Podemos usar este comparador personalizado así:

priority_queue, vector>, myComparator> pq;

Ejemplo de uso de cola de prioridad con comparador personalizado

Supongamos que queremos encontrar los k elementos con la mayor suma en dos vectores. Podemos usar una cola de prioridad para mantener los elementos con la mayor suma y un comparador personalizado para definir el orden de los pares:

typedef pair> ppi;

vector a = {1, 7, 11};
vector b = {3, 4, 9};

int k = 4;

priority_queue, greater> pq;

for(int i = 0; i < a.size(); i++){
    for(int j = 0; j < b.size(); j++){
        int sum = a[i] + b[j];
        if(pq.size() < k){
            pq.push({sum, {i, j}});
        }
        else{
            if(sum > pq.top().first){
                pq.pop();
                pq.push({sum, {i, j}});
            }
        }
    }
}

cout << "Los " << k << " pares con la mayor suma son:" << endl;

vector> res;

while(!pq.empty()){
    int i = pq.top().second.first;
    int j = pq.top().second.second;
    res.push_back({a[i], b[j]});
    pq.pop();
}

sort(res.begin(), res.end(), greater>());

for(auto p: res){
    cout << "(" << p.first << ", " << p.second << ")" << endl;
}

Este programa imprimirá los cuatro pares con la mayor suma y sus valores correspondientes de los vectores.

Conclusión

Una cola de prioridad es una estructura importante que se utiliza en muchos problemas de programación y se implementa en C ++ mediante la plantilla de clase priority_queue. A veces, necesitamos una cola de prioridad con un orden personalizado definido por un comparador. En tales escenarios, podemos definir nuestro propio comparador personalizado y usarlo para definir la cola de prioridad.

Preguntas frecuentes

¿Por qué necesito un comparador personalizado para una cola de prioridad?

En algunos casos, queremos ordenar objetos según uno de sus atributos en lugar de su orden natural. Por ejemplo, queremos ordenar los pares de acuerdo con el primer elemento en lugar del segundo. Un comparador personalizado nos permite hacer esto en una cola de prioridad.

¿Puedo usar una función como comparador personalizado?

Sí, podemos usar una función o una clase como un comparador personalizado para una cola de prioridad.

¿Puedo usar la función sort() con una cola de prioridad?

No, la función sort() solo funciona con contenedores que implementan iteradores aleatorios, mientras que una cola de prioridad se implementa generalmente con un contenedor secuencial.
[nekopost slugs="isalnum-c,cpp-strftime,generar-flotadores-aleatorios-cpp,temporizador-de-la-funcion-cpp,convertir-char-int-cpp,resolver-iso-cpp-prohibe-el-error-de-comparacion,cadena-dividida-usando-delimitador-cpp,funcion-getline-cpp,eliminar-la-matriz-en-cpp"]