Build a delayed task scheduler

Why does the heap need a sequence number as well as the due time?

For two reasons. Tasks due at the same moment should start in the order they were scheduled, and a heap keyed on the due time alone does not keep that order: pushing six tasks due together and popping them gave a, c, f, e, b, d in a recorded run. And if the task itself were the second item of a tuple, a tie on the due time would make Python compare two functions, which raises a TypeError. A counter taken at schedule time settles every tie, and nothing after it is ever compared.

Why must scheduling an earlier task wake the dispatcher?

Because the dispatcher is asleep in a timed wait worked out for the old head of the heap, and nothing else will end that wait before the old head is due. If the new task is due sooner, it waits for the old deadline and starts late. In the recorded run, a task due at tick 3 started at tick 6 without the notify and at tick 3 with it. The rule is one comparison: notify when the new entry is the new top of the heap.

How do you cancel a task that is in the middle of a heap?

You mark it and leave it where it is. heapq has no way to remove an item from the middle, and doing it by hand means finding the item, which is O(n), and restoring the heap, which is O(n) again; the standard library's sched module does exactly that on every cancel. Marking the entry is O(1), and the dispatcher discards a cancelled entry when it reaches the top, at the cost of a pop it would have made anyway. What you pay instead is memory, until the cancelled entry's due time comes round.

Why run tasks on a pool rather than on the dispatcher thread?

Because a task that takes a while holds whichever thread runs it, and if that thread is the dispatcher, no other task can start until it returns, however overdue. In the recorded run a task due at tick 3 started at tick 5, behind a task that took three ticks. Handing each due task to a pool keeps the dispatcher doing one thing, waiting for the next due time. A task that raises is then caught on a worker, logged and counted, and the dispatcher never sees it.

What should shutdown do with tasks that are not due yet?

Decide it out loud, because each answer has a cost. This build stops accepting new tasks at once, hands back every task still in the heap so the caller can persist or drop them, and waits for tasks already running to finish. Running the waiting tasks early would break the promise that nothing runs before its time, and waiting for them could keep a process alive for hours. Dropping them silently is the one choice to rule out, because nobody can tell afterwards what was lost.