11 · Colas de prioridad
Buscar soluciones eficientes · Ruta de Aprendizaje
Antes de empezar. Vectores y pares: 03 - Arreglos y búsqueda lineal y 06 - Conjuntos, mapas y pares; costos: 07 - Cuánto se demora tu programa.
🎯 Objetivos
Al terminar este módulo sabes:
- Usar
priority_queuecomo max-heap y como min-heap. - Aplicar los patrones “el extremo una y otra vez” y “top-K”.
- Elegir entre heap,
setysortsegún lo que el problema repite.
📖 La lección
Llegan tareas con prioridades 4, 9 y 6. Se atiende la de prioridad 9; después llega una de prioridad 8. La siguiente debe ser 8. Buscar el máximo recorriendo todas las tareas sirve, pero repetirlo tras cada llegada o salida cuesta O(n) por atención. Un heap conserva solo el orden necesario para consultar y retirar ese extremo eficientemente.
| Operación | Prioridades pendientes (mostradas ordenadas para leer) | Próxima |
|---|---|---|
| llegan 4, 9, 6 | 4, 6, 9 | 9 |
| atender | 4, 6 | 6 |
| llega 8 | 4, 6, 8 | 8 |
Una cola común atendería por orden de llegada; aquí manda la prioridad.
La promesa del heap
Una priority_queue mantiene siempre el mayor arriba: push y pop
cuestan O(log n) y top es O(1).
priority_queue<int> maxheap; // el mayor arriba
priority_queue<int, vector<int>, greater<int>> minheap; // el menor arribaEn el min-heap, int es el tipo de dato, vector<int> es el almacenamiento interno y greater<int> invierte la comparación para dejar el menor arriba. No tienes que manejar ese vector por separado. Para pares,
priority_queue<pair<int,int>> compara por .first — mete la prioridad ahí.
Insertar, consultar y retirar
priority_queue<int> pendientes;
pendientes.push(4);
pendientes.push(9);
pendientes.push(6);
cout << pendientes.top() << "\n"; // 9: consultar no lo retira
pendientes.pop(); // retira el 9, no devuelve su valor
pendientes.push(8); // llega una tarea nueva
cout << pendientes.top() << "\n"; // 8: ahora supera al 6
while (!pendientes.empty()) pendientes.pop();empty() dice si está vacío. Antes de top() o pop() debe haber al menos
un elemento. Un min-heap usa las mismas operaciones, pero entrega el menor.
Para un par, un empate en .first se resuelve comparando .second.
Por qué basta un orden parcial
Por dentro es un heap (un árbol casi completo guardado en un arreglo) — la ficha priority_queue (heap) lo explica con el detalle que quieras; para usarla basta su contrato. Pero vale la pena ver la forma una vez, porque explica el costo:
Si el diagrama no cabe, deslízalo horizontalmente.
Lo único que el heap promete es que cada padre es mayor o igual que sus hijos. No está ordenado (7 y 8 son hermanos, sin orden entre ellos), y por eso puede ser tan barato: meter o sacar un elemento solo arregla un camino entre la raíz y una hoja, que en un árbol casi completo mide log n.
El patrón “el extremo, una y otra vez”
sort sirve cuando ordenas una vez. El heap brilla cuando el proceso es
sacar el extremo → transformarlo → posiblemente devolverlo, muchas veces:
la colección cambia entre consultas. Si hacemos q operaciones y hay hasta n
elementos, ordenar de nuevo cada vez puede costar O(q·n log n); extraer e
insertar en el heap cuesta O(log n) por operación.
Ejemplo: atender trabajo pendiente. Hay tareas con 8, 5 y 3 unidades pendientes. Cada turno atiende la que tiene más, le quita 4 unidades y la reinserta solo si aún queda trabajo. Si quedan menos de 4, la termina.
| Turno | Pendientes antes | Se atiende | Pendientes después |
|---|---|---|---|
| 1 | {8, 5, 3} | 8 → 4 | {5, 4, 3} |
| 2 | {5, 4, 3} | 5 → 1 | {4, 3, 1} |
| 3 | {4, 3, 1} | 4 → 0 | {3, 1} |
Las llaves muestran los valores ordenados para leer la traza; no son
el arreglo interno del heap. Observa que el siguiente máximo puede cambiar
después de cada turno: no sirve recorrer una única ordenación inicial.
En cada turno hacemos top() para recordar el valor, pop() para retirarlo
y, si su nuevo valor es positivo, push() para devolverlo. Consultar top()
por sí solo no retira ni modifica la tarea.
El patrón top-K
Los K mayores de un flujo enorme, sin ordenar todo: un min-heap de tamaño K donde el más chico de los grandes vigila la puerta.
// supone: int K; vector<int> datos; // ya leídos
priority_queue<int, vector<int>, greater<int>> topk;
for (int x : datos) {
topk.push(x);
if ((int)topk.size() > K) topk.pop(); // expulsa al más chico
}
// para K >= 0 quedan min(K, n) valores: los mayores del flujoTraza con datos = {5, 1, 8, 3, 9, 2} y K = 3 (el heap se muestra ordenado
para leerlo; por dentro solo garantiza el mínimo arriba):
| llega | tras push | ¿más de 3? | tras pop (sale el mínimo) |
|---|---|---|---|
| 5 | {5} | no | {5} |
| 1 | {1, 5} | no | {1, 5} |
| 8 | {1, 5, 8} | no | {1, 5, 8} |
| 3 | {1, 3, 5, 8} | sí → sale 1 | {3, 5, 8} |
| 9 | {3, 5, 8, 9} | sí → sale 3 | {5, 8, 9} |
| 2 | {2, 5, 8, 9} | sí → sale 2 | {5, 8, 9} |
Si el diagrama no cabe, deslízalo horizontalmente.
El que está arriba es siempre el más chico de los K grandes: si el que llega no lo supera, entra y sale de inmediato; si lo supera, se queda y el portero cambia. Como el heap nunca tiene más de K + 1 elementos, cada operación cuesta O(log(K + 1)); se hacen O(n) operaciones. Si K = 0, se descarta todo en O(n).
¿Heap, set o sort?
| El problema repite… | Usa |
|---|---|
| sacar el mayor/menor y meter cosas nuevas | priority_queue |
| buscar, insertar y borrar valores arbitrarios | set / multiset |
| una sola pasada sobre datos fijos | sort y listo |
El heap no sabe borrar del medio ni buscar; a cambio, su constante es más
liviana que la del set. Ficha completa en priority_queue (heap) (cómo
funciona por dentro y todas sus operaciones) y comparación con el resto en el
Catálogo de estructuras.
🏋️ Práctica
Práctica directa: Atender prioridades
Lee q (1 a 1000) y q operaciones: AGREGA x inserta un entero; ATIENDE imprime y retira el máximo, o VACIA si no hay tareas. Entrada: 7 / AGREGA 4 / AGREGA 9 / AGREGA 6 / ATIENDE / AGREGA 8 / ATIENDE / ATIENDE. Salida: 9 / 8 / 6.
En los ejemplos de entrada y salida, / separa líneas; no se escribe en el archivo.
Idea para comprobar tu solución
Usa un max-heap: push al agregar; al atender comprueba empty antes de top y pop. Una operación más atiende el 4; la siguiente imprime VACIA.
Variación: Atender y devolver lo pendiente
Hay tareas con 7, 6 y 2 unidades pendientes. En cada turno atiende la mayor,
réstale 4 y devuélvela solo si queda trabajo. Imprime los valores que atiendes
hasta vaciar la colección. La salida debe ser 7 6 3 2 2.
Una pista, si la necesitas
Después de atender 7 queda 3, pero la siguiente tarea es la de 6. La prioridad cambia.
Contrastar el razonamiento
Los pendientes pasan por {7,6,2}, {6,3,2}, {3,2,2}, {2,2}, {2} y {}. Guarda top antes de pop; reinserta solo un resto positivo. Los dos 2 son tareas distintas y deben conservarse.
Aplicar en problemas
Los problemas siguientes requieren traducir un enunciado y pueden combinar otras ideas. Su procedencia e idioma no indican un orden obligatorio de dificultad.
Una aplicación con juez (inglés)
Powerful Discount Tickets — AtCoder ABC141 D pide distribuir descuentos entre precios para minimizar la suma final. Cada descuento divide un precio por dos, redondeando hacia abajo. Los precios cambian durante el proceso: es una aplicación de prioridades dinámicas con una decisión greedy que debes justificar.
Una pista, si la necesitas
Aplicar un descuento a un precio x ahorra
x − x/2, usando división entera. Compara el ahorro de los precios actuales y observa qué pasa con los descuentos siguientes sobre el mismo producto.
Contrastar el razonamiento
El mayor precio actual ofrece un ahorro máximo. Para cada producto, los ahorros de sus descuentos sucesivos nunca aumentan; elegir el mayor ahorro disponible permite combinar esas secuencias en orden. Un max-heap extrae un precio y reinserta su mitad. La suma final necesita
long long: puede superar el rango de int.
Contrastar estructuras en problemas (inglés)
Estos problemas permiten decidir si hacen falta prioridades dinámicas. Gifts Fixing utiliza mínimos como referencia; Social Network B2 combina orden de llegada y pertenencia (cola/deque y conjunto). No son aplicaciones directas obligatorias del heap: compara sus necesidades con el ejercicio de prioridades de esta clase.
| # | Problema | Dificultad | Qué practica |
|---|---|---|---|
| 1 | Gifts Fixing (1399B) | ★ (800) | mínimos como referencia |
| 2 | Olya and Game with Arrays (1859B) | ★★ (1000) | extremos por grupo |
| 3 | Minimum Extraction (1607C) | ★★ (1000) | “sacar el mínimo” repetido (¿de verdad necesitas el heap?) |
| 4 | ⭐ Social Network (hard) (1234B2) | ★★★ (1300) | cola + set trabajando juntos |
Desafío OCI (en español)
| Problema | Fase | Qué practica |
|---|---|---|
| Las mejores peores películas | Nacional 2025 | estructuras con prioridad, en acción |
Un ejemplo para pensar
Queremos conservar los dos números mayores mientras llegan 6, 2, 9, 5.
Si el heap debe expulsar un elemento cada vez que supera tamaño dos,
¿conviene tener el mayor o el menor arriba?
Si el diagrama no cabe, deslízalo horizontalmente.
Arriba debe estar el candidato a salir
Un min-heap conserva primero
{2, 6}. Al llegar 9, expulsa el 2 y quedan{6, 9}. Al llegar 5, expulsa ese mismo 5. Un max-heap expulsaría el 9 justo cuando interesa conservarlo. El mínimo del grupo es el que decide la entrada de nuevos candidatos, aunque la pregunta pida los mayores.
← 10 - Algoritmos numéricos y aritmética modular · Ruta de Aprendizaje · 12 - Búsqueda binaria sobre la respuesta →