La estructura de datos priority_queue (cola de prioridad) es un componente valioso dentro de la Biblioteca Estándar de C++. A diferencia de una cola FIFO tradicional, priority_queue organiza sus elementos basándose en una prioridad definida, permitiendo el acceso rápido y la extracción del elemento con la mayor (o menor) prioridad.

Principios Fundamentales

• Implementación subyacente: Por defecto, priority_queue se apoya en un std::vector como contenedor subyacente y utiliza algoritmos como push_heap y pop_heap para mantener la propiedad de montículo (heap).
• Criterio de ordenación: La confiugración predeterminada es un montículo máximo (std::less<T>), donde el elemento más grande reside en la cima. Se puede invertir este comportamiento a un montículo mínimo (std::greater<T>) especificando un comparador diferente.
• Complejidad temporal: Las operaciones de inserción (push) y eliminación (pop) tienen una complejidad logarítmica (O(log n)). La recuperación del elemento superior (top) es una operación de tiempo constante (O(1)).

Operaciones Comunes

Instanciación

Para crear una priority_queue:

#include <queue>
#include <vector>
#include <functional> // Para std::greater

// Cola de prioridad predeterminada (montículo máximo)
std::priority_queue<int> maxHeap;

// Cola de prioridad de montículo mínimo
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

// Inicialización a partir de un rango de elementos
std::vector<int> data = {5, 2, 8, 1, 9};
std::priority_queue<int> initializedHeap(data.begin(), data.end());

Manipulación de Elementos

Añadir y quitar elementos:

maxHeap.push(15); // Añade un elemento
if (!maxHeap.empty()) {
   maxHeap.pop(); // Elimina el elemento de mayor prioridad
}

Acceso al Elemento Superior

Para ver el elemento de mayor prioridad sin eliminarlo:

if (!maxHeap.empty()) {
   int highestPriority = maxHeap.top();
   // ... usar highestPriority ...
}

Verificación de Estado

Comprobar si la cola de prioridad está vacía y obtener su tamaño:

bool isEmpty = maxHeap.empty();
size_t elementCount = maxHeap.size();

Criterios de Prioridad Personalizados

Para tipos de datos definidos por el usuario, se necesita proporcionar una forma de comparar sus prioridades. Esto se puede lograr sobrecargando el operador de comparación o definiendo una función de comparador personalizada.

Sobrecarga del Operador de Comparación

struct Job {
   int urgency;
   std::string description;

   // Permite la ordenación predeterminada para montículo máximo
   bool operator<(const Job& other) const {
       return urgency < other.urgency;
   }
};

std::priority_queue<Job> jobQueue;
jobQueue.push({3, "Process Data"});
jobQueue.push({5, "Send Notification"}); // Mayor urgencia

Función de Comparador Personalizada (Functor o Lambda)

Alternativamente, se puede pasar un comparador como argumento de plantilla:

struct Job {
   int urgency;
   std::string description;
};

// Comparador para montículo mínimo basado en urgencia
auto jobComparator = [](const Job& a, const Job& b) {
   return a.urgency > b.urgency; // Montículo mínimo
};

std::priority_queue<Job, std::vector<Job>, decltype(jobComparator)> minUrgencyQueue(jobComparator);
minUrgencyQueue.push({3, "Process Data"});
minUrgencyQueue.push({5, "Send Notification"});

Ejemplo Práctico: Combinación de K Listas Ordenadas

La priority_queue es ideal para problemas como la combinación de múltiples listas o arrays ordenados. Aquí un ejemplo de cómo resolver el LeetCode 23:

#include <vector>
#include <queue>

// Definición de ListNode (asumiendo que está disponible)
struct ListNode {
   int val;
   ListNode *next;
   ListNode(int x) : val(x), next(nullptr) {}
};

class Merger {
public:
   // Comparador para el montículo mínimo de nodos de lista
   struct NodeComparator {
       bool operator()(ListNode* left, ListNode* right) {
           // Queremos el nodo con el valor más pequeño en la cima
           return left->val > right->val;
       }
   };

   ListNode* mergeKLists(std::vector<ListNode*>& lists) {
       // Cola de prioridad que almacena punteros a ListNode, usando nuestro comparador
       std::priority_queue<ListNode*, std::vector<ListNode*>, NodeComparator> minHeap;

       // Añadir el primer nodo de cada lista no vacía al montículo
       for (ListNode* listHead : lists) {
           if (listHead != nullptr) {
               minHeap.push(listHead);
           }
       }

       // Nodo centinela para construir la lista resultante
       ListNode dummyHead(0);
       ListNode* current = &dummyHead;

       // Procesar el montículo hasta que esté vacío
       while (!minHeap.empty()) {
           ListNode* smallestNode = minHeap.top();
           minHeap.pop();

           // Adjuntar el nodo más pequeño a la lista resultante
           current->next = smallestNode;
           current = current->next;

           // Si el nodo extraído tiene un sucesor, añadirlo al montículo
           if (smallestNode->next != nullptr) {
               minHeap.push(smallestNode->next);
           }
       }

       return dummyHead.next; // Devolver el inicio de la lista combinada
   }
};

Consideraciones Importantes

• priority_queue no soporta la iteración directa; el acceso se limita al elemento de mayor prioridad mediante top().
• Para escenarios con inserciones y eliminaciones frecuentes, priority_queue generalmente supera a un array ordenado mantenido manualmente.
• Las implementaciones de STL no son intrínsecamente seguras para hilos. Se deben emplear mecanismos de sincronización externos si se accede a una priority_queue desde múltiples hilos.

La capacidad de priority_queue para manejar prioridades personalizadas y su eficiencia en operaciones clave la convierten en una herramienta indispensable para una variedad de algoritmos y problemas de gestión de colas.