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_queue como max-heap y como min-heap.
  • Aplicar los patrones “el extremo una y otra vez” y “top-K”.
  • Elegir entre heap, set y sort segú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ónPrioridades pendientes (mostradas ordenadas para leer)Próxima
llegan 4, 9, 64, 6, 99
atender4, 66
llega 84, 6, 88

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 arriba

En 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:

91728334552667el número chico es la posición en el arreglotop() = 9: el mayor siempre arriba91728334552667el mismo heap, como arreglohijos de i: 2i y 2i+1padre de i: i / 2cada padre ≥ sus hijos; nada más se promete(7 y 8 son hermanos: entre ellos no hay orden)por eso push y pop cuestan O(log n): solo se recorre un camino raíz–hoja

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.

TurnoPendientes antesSe atiendePendientes 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 flujo

Traza 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):

llegatras 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}
los 3 mayores hasta ahora: {3, 5, 8}358top(): el menorllega 9sale 39 > 3: entra, y el 3 (el más chico) se vaahora {5, 8, 9}589top(): el menorllega 2sale 22 < 5: entra y sale al instante: no es top-3tras insertar puede haber K+1; tras eliminar sobran a lo más K

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 nuevaspriority_queue
buscar, insertar y borrar valores arbitrariosset / multiset
una sola pasada sobre datos fijossort 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.

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.

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.

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.

#ProblemaDificultadQué practica
1Gifts Fixing (1399B)★ (800)mínimos como referencia
2Olya and Game with Arrays (1859B)★★ (1000)extremos por grupo
3Minimum 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)

ProblemaFaseQué practica
Las mejores peores películasNacional 2025estructuras 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?

Después de insertar 6, 2 y 9min-heap269top()max-heap926top()pop() retira la raíz. ¿Cuál conviene expulsar?

Si el diagrama no cabe, deslízalo horizontalmente.


← 10 - Algoritmos numéricos y aritmética modular · Ruta de Aprendizaje · 12 - Búsqueda binaria sobre la respuesta →