Lista de eventos futuros

01 · Punto de partida

Del papel ordenado a la máquina ordenada

En el Tema 13 la agenda era una lista con sort tras cada append y pop(0) para sacar lo próximo. Con 8 eventos funciona; con 80 000 (un año de banco) cada pop(0) corre 80 000 lugares y cada sort reordena todo: la simulación se pasa más tiempo ordenando que simulando.

La solución es la lista de eventos futuros (FEL) como cola de prioridad (heap): una estructura que mantiene “lo mínimo arriba” sin ordenar todo. push y pop cuestan O(log n) y el próximo siempre está en fel[0].

• ¿Cuánto cuesta sacar lo próximo con lista vs. heap?
• ¿Qué formato evita comparar diccionarios y romper el programa?
• ¿Cómo se resuelven empates sin azar del programa?
• ¿Cómo se mira lo próximo sin sacarlo y cómo se cancela?

02 · Definición

Heap, tupla y contador: el trío inseparable

03 · Formato canónico

Cinco campos en orden sagrado

1. 1
   t (float).

   Tiempo del evento. Manda siempre: lo más temprano sale primero.

2. 2
   prio (int).

   Regla de empates: 0 salidas, 1 llegadas, 2 fin de simulación. Se fija una vez por tipo.

3. 3
   seq (int).

   Contador global que crece: garantiza desempate total y orden FIFO entre gemelos. Nunca se reutiliza.

4. 4
   tipo + datos.

   Viajan al final porque nunca deben compararse: dos dicts no tienen orden y lanzarían TypeError.

Peek (ver sin sacar)

fel[0] es lo próximo sin extraerlo: sirve para chequear fin (“¿lo próximo supera T?”) sin avanzar.

Cancelación perezosa

Borrar en un heap es caro: se marca el evento como inválido (datos["ok"]=False) y al extraerlo se descarta sin procesar.

No iterar ordenado

El heap solo garantiza el mínimo arriba; el resto está desordenado a propósito. Para listar ordenado hay que hacer sorted(fel) (solo para depurar).

Calendario vs. FEL

Calendario = idea de agenda (Tema 13); FEL = heap que la implementa (este tema). Misma información, distinta máquina.

04 · Ejemplos

La misma agenda, máquina nueva

05 · Representación en Python

heapq en cinco líneas

Todo el Tema 14 cabe en heappush / heappop / fel[0] más un contador global. El segundo bloque muestra el desempate que salva al programa.

import heapq, itertools
fel, seq = [], itertools.count()
def agendar(t, prio, tipo, datos=None):
    heapq.heappush(fel, (t, prio, next(seq), tipo, datos or {}))

agendar(4.0, 1, "llegada", {"id": "C2"})
agendar(2.0, 1, "llegada", {"id": "C1"})
agendar(5.0, 0, "salida", {"caja": 1})
print("próximo sin sacar:", fel[0][3], fel[0][0])
while fel:
    t, prio, _, tipo, datos = heapq.heappop(fel)
    print(round(t, 1), tipo, datos)

import heapq, itertools
fel, seq = [], itertools.count()
# Mismo tiempo, distinta prioridad: sale primero aunque llegó después
heapq.heappush(fel, (5.0, 1, next(seq), "llegada", {"id": "C9"}))
heapq.heappush(fel, (5.0, 0, next(seq), "salida", {"caja": 1}))
print([heapq.heappop(fel)[3] for _ in range(len(fel))])  # ['salida', 'llegada']

06 · Exploración

Laboratorio: por qué el heap gana

Elegí cuántos eventos n tendrá la agenda. La barra gris estima el trabajo de la lista (pop(0) desplaza todo: ~n²/2 movimientos) y la lima el del heap (~n·log₂n). Con n=100 empatan a ojo; con n=2000 la gris se vuelve una torre. Debajo, la agenda generada muestra que ambas entregan lo mismo: solo cambia el costo.

Barras en escala proporcional (la gris crece cuadrática, la lima casi lineal). La agenda determinista de n tiempos confirma que el mínimo coincide.

Preguntas para explorar

1. Con n=100, ¿cuántas veces más barato es el heap? ¿Y con n=2000?
2. Si cada operación costara 1 µs, ¿cuánto tardaría cada método con n=2000?
3. ¿Por qué el mínimo coincide aunque las tripas sean distintas?

07 · Comprensión

Confusiones frecuentes

08 · Práctica guiada

Ejercicios con Python

Ejercicio 1: peek sin sacar

Mirá lo próximo dos veces y comprobá que no se gasta.

import heapq
fel = [(2.0, 1, 0, "llegada", {}), (5.0, 0, 1, "salida", {})]
heapq.heapify(fel)
print("peek:", fel[0][:2], "| tamaño:", len(fel))
print("peek otra vez:", fel[0][:2], "| tamaño:", len(fel))

Ejercicio 2: romperlo sin contador

¿Qué pasa con dos gemelos sin seq?

import heapq
fel = [(5.0, "llegada", {"id": "A"}), (5.0, "llegada", {"id": "B"})]
try:
    heapq.heapify(fel)
    print(heapq.heappop(fel))
except TypeError as e:
    print("TypeError:", str(e)[:60])

Ejercicio 3: cancelación perezosa

Marcá un futuro como inválido y filtralo al extraer.

import heapq, itertools
fel, seq = [], itertools.count()
heapq.heappush(fel, (4.0, 1, next(seq), "llegada", {"id": "C5", "ok": True}))
ev = (6.0, 1, next(seq), "llegada", {"id": "C6", "ok": True})
heapq.heappush(fel, ev)
ev[4]["ok"] = False  # C6 abandona: se cancela
while fel:
    t, _, _, tipo, datos = heapq.heappop(fel)
    if not datos.get("ok", True):
        print("descarto", datos["id"])
        continue
    print("proceso", datos["id"])

09 · Síntesis

Ideas para recordar

En el próximo tema haremos la inicialización del modelo: reloj en cero, estado inicial y primeros futuros.