Priority & scheduling
Schedule the next piece of work without sorting everything again.
BY THE END, YOU CAN
- Explain the heap invariant
- Use deterministic tie-breaking
- Recognize starvation and cancellation tradeoffs
Diagram description: 1 · urgent → 3; 1 · urgent → 2; 3 → 7; 3 → 4; 2 → 5; 2 → 9; Ties: (priority, arrival order)
Only the next item must be cheap
A priority queue returns the item with the highest scheduling priority rather than the oldest item.
Python's heapq uses a min-heap: the smallest item is at the root, and each parent is no greater than its children. The entire collection is not sorted. Insertion and removal of the smallest item take logarithmic time, while inspecting it is constant time.
A heap fits delayed jobs because Relay repeatedly asks which scheduled time comes next, rather than needing a fully sorted report.
Make equal priorities deterministic
Store a tuple containing the scheduling key, an increasing sequence number, and the job.
Python compares tuple fields in order. The sequence number preserves insertion order among equal keys and prevents Python from comparing job objects that may not support ordering. For delayed work, the worker must also compare the earliest due time with the current time before executing it.
Removing the earliest scheduled job does not imply it is ready now. Treat the clock as an input in tests.
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)Fairness is part of correctness
If urgent jobs always arrive, low-priority work may never run.
That is starvation. Possible policies include aging waiting work, reserving capacity for each priority, or defining separate service objectives. Each changes the scheduler's promise.
Removing arbitrary heap entries is also less convenient than removing the minimum; a common approach marks cancelled entries and skips them later, then periodically rebuilds if stale entries accumulate. Data-structure choice should include these operational behaviors rather than considering only the simplest happy-path operation.
COMMON FAILURE MODE
Assuming the array backing a heap is fully sorted, or allowing equal priorities to trigger comparisons between incompatible job objects.
TRY IT YOURSELF
Schedule three jobs with two equal due times. Add sequence numbers and show the exact removal order. Describe a policy that prevents low-priority starvation.
Make the call in the laboratory.
The two-question checkpoint, your notes, and your saved progress are in the laboratory. Free, with no account.
Open in the laboratory ↗CONNECT IT TO RELAY
Add delayed jobs to Relay using a heap. Inject a fake current time so readiness tests do not actually sleep.