Estructura de datos - Cola de prioridad
La cola de prioridad (Priority Queue) es una forma extendida de la cola. A diferencia de la cola normal, que sigue el principio de "primero en entrar, primero en salir", en la cola de prioridad cada elemento tiene asignada una prioridad, y la operación de desencolar siempre extrae el elemento con la prioridad más alta de la cola actual.
Concepto y características de la cola de prioridad
Se puede comparar con el sistema de triaje de la sala de emergencias de un hospital: los pacientes con condiciones más urgentes, incluso si llegan después, son atendidos primero.
Las operaciones principales de la cola de prioridad difieren de las de la cola normal:
| Operación | Cola normal | Cola de prioridad |
|---|---|---|
| Encolar (enqueue) | Agregar elemento al final de la cola | Insertar elemento con su prioridad |
| Desencolar (dequeue) | Devuelve el elemento al frente de la cola (el primero en entrar) | Devuelve el elemento con mayor prioridad |
Comparación de tres métodos de implementación
Matriz desordenada
Lista enlazada ordenada
Montón (Heap) ★Recomendado
La implementación con montón es la óptima: equilibra la eficiencia de inserción y desencolado, y es una dependencia central de algoritmos como el camino más corto de Dijkstra y la codificación de Huffman.
La figura anterior compara las diferencias de complejidad temporal de los tres métodos de implementación; la implementación con montón es la opción más equilibrada.
Implementación basada en matriz desordenada
Ejemplo
#define MAX 100
/* Cola de prioridad basada en matriz desordenada (cola de máxima prioridad: cuanto mayor el valor, mayor la prioridad) */
struct PriorityQueue {
int items[MAX];
int size; /* Número actual de elementos */
};
void initPQ(struct PriorityQueue* pq) { pq->size = 0; }
/* Encolar: agregar directamente al final, O(1) */
void enqueue(struct PriorityQueue* pq, int value) {
if (pq->size >= MAX) return;
pq->items[pq->size++] = value;
}
/* Desencolar: recorrer para encontrar el valor máximo, O(n)
Después de encontrarlo, mover el último elemento a la posición eliminada y reducir size en 1 */
int dequeue(struct PriorityQueue* pq) {
if (pq->size == 0) return -1;
/* Encontrar el índice del valor máximo */
int maxIdx = 0;
for (int i = 1; i < pq->size; i++) {
if (pq->items[i] > pq->items[maxIdx]) {
maxIdx = i;
}
}
int maxVal = pq->items[maxIdx];
/* Mover el último elemento a la posición eliminada (evita muchos movimientos) */
pq->items[maxIdx] = pq->items[--pq->size];
return maxVal;
}
int main() {
struct PriorityQueue pq;
initPQ(&pq);
enqueue(&pq, 5);
enqueue(&pq, 9);
enqueue(&pq, 3);
enqueue(&pq, 7);
printf("Desencolar (mayor prioridad): %d\n", dequeue(&pq)); /* Salida: 9 */
printf("Desencolar (mayor prioridad): %d\n", dequeue(&pq)); /* Salida: 7 */
printf("Desencolar (mayor prioridad): %d\n", dequeue(&pq)); /* Salida: 5 */
printf("Desencolar: %d\n", dequeue(&pq)); /* Salida: 3 */
return 0;
}
Implementación basada en lista enlazada ordenada
Ejemplo
#include <stdlib.h>
struct Node {
int data;
int priority; /* Prioridad (cuanto mayor el valor, mayor la prioridad) */
struct Node* next;
};
/* Encolar: insertar en orden descendente de prioridad, O(n) */
struct Node* enqueue(struct Node* head, int data, int priority) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->priority = priority;
newNode->next = NULL;
/* Lista vacía o el nuevo nodo tiene la mayor prioridad → insertar al inicio */
if (head == NULL || head->priority < priority) {
newNode->next = head;
return newNode;
}
/* Recorrer para encontrar la posición adecuada (mantener orden descendente) */
struct Node* cur = head;
while (cur->next != NULL && cur->next->priority >= priority) {
cur = cur->next;
}
newNode->next = cur->next;
cur->next = newNode;
return head;
}
/* Desencolar: eliminar el nodo cabeza (mayor prioridad), O(1) */
struct Node* dequeue(struct Node* head) {
if (head == NULL) return NULL;
struct Node* temp = head;
printf("Desencolar: data=%d, priority=%d\n", temp->data, temp->priority);
head = head->next;
free(temp);
return head;
}
int main() {
struct Node* pq = NULL;
pq = enqueue(pq, 10, 1); /* Dato 10, prioridad 1 */
pq = enqueue(pq, 20, 5); /* Dato 20, prioridad 5 */
pq = enqueue(pq, 30, 3); /* Dato 30, prioridad 3 */
pq = dequeue(pq); /* Desencolar: data=20, priority=5 (prioridad más alta) */
pq = dequeue(pq); /* Desencolar: data=30, priority=3 */
pq = dequeue(pq); /* Desencolar: data=10, priority=1 */
return 0;
}
Montón (Heap)Es el método más común y equilibrado para implementar una cola de prioridad: tanto insertar como extraer el elemento de mayor prioridad se realizan en tiempo O(log n). Este contenido se ampliará en detalle en el Capítulo 15, Montón.
Escenarios de aplicación
| Escenario | Descripción |
|---|---|
| Programación de tareas | El sistema operativo determina el orden de ejecución de la CPU según la prioridad de las tareas |
| Camino más corto de Dijkstra | Cada vez selecciona el nodo no visitado con la distancia mínima; depende de la cola de prioridad |
| Codificación de Huffman | Extrae repetidamente los dos nodos de menor frecuencia y los fusiona para construir el árbol de codificación óptimo |