Prioridad y planificación

Solo el siguiente elemento debe ser barato

Una cola de prioridad devuelve el elemento con mayor prioridad de planificación en lugar del más antiguo. heapq de Python usa un min-heap (montículo de mínimos): el elemento más pequeño está en la raíz y cada padre es menor o igual que sus hijos.

La colección completa no está ordenada. Insertar y quitar el mínimo toma tiempo logarítmico; consultarlo, tiempo constante. Un heap encaja con los trabajos diferidos porque Relay pregunta una y otra vez qué hora programada viene después, no necesita un reporte completamente ordenado.

Haz deterministas las prioridades iguales

Guarda una tupla con la clave de planificación, un número de secuencia creciente y el trabajo.

Python compara los campos de una tupla en orden. El número de secuencia conserva el orden de inserción entre claves iguales y evita que Python compare objetos de trabajo que quizá no se puedan ordenar. Para trabajo diferido, el worker además debe comparar la hora de vencimiento más cercana con la hora actual antes de ejecutarlo: sacar el trabajo programado más temprano no implica que ya esté listo.

En las pruebas (tests), trata el reloj como una entrada.

import heapq

schedule = []
heapq.heappush(schedule, (10, 0, "email"))
heapq.heappush(schedule, (5, 1, "report"))
due_at, sequence, job = heapq.heappop(schedule)
print(due_at, job)

La equidad también es corrección

Si siempre llegan trabajos urgentes, el trabajo de baja prioridad puede no ejecutarse nunca.

Eso se llama inanición (starvation). Algunas políticas posibles son «envejecer» el trabajo en espera, reservar capacidad para cada prioridad o definir objetivos de servicio separados. Cada una cambia la promesa del planificador.

Quitar entradas arbitrarias de un heap también es menos cómodo que quitar el mínimo; una solución común es marcar las entradas canceladas, saltarlas después y reconstruir el heap de vez en cuando si se acumulan entradas obsoletas. Elegir una estructura de datos debe incluir estos comportamientos operativos y no solo la operación más simple del caso feliz.