TimeService: Scheduling with an Indexed Min-Heap

A timer service must answer two different questions: which timer fires next, and where is the timer with a given id? A single array can answer both, but one of those operations becomes expensive as the collection grows.

The four operations are not equal. advance only cares about the earliest deadline. cancel and edit only care about a specific id. One data structure is good at one of those questions. Two structures, kept in lockstep, answer both.

Why an array alone is not enough

Imagine timers as { id, fireTime } in a JavaScript array, sorted by fireTime.

▸Peeking at the next due timer is O(1).
▸Firing it with shift() is O(n) because every later element slides down.
▸Finding id "job_47" to cancel it is O(n), followed by O(n) movement after splice().
▸Editing a timer is O(n) to find it, followed by repositioning it to keep the array sorted.

People patch this with a second array, a filter, or a tombstone flag (cancelled: true). Tombstones make advance skip dead nodes, but the heap (or array) fills with garbage until you compact. Under a burst of cancels you have paid O(n) to discover each id, then you still walk dead entries on every tick.

The gotcha is not “arrays are slow.” It is that id lookup and “what is next?” are different questions. A structure optimized for one will punish the other unless you store a second index.

Why the min-heap and ID index work together

A binary min-heap stored in an array gives:

▸Next timer at index 0 — O(1) peek.
▸Insert and delete-min in O(log n) after the tree is repaired with siftUp / siftDown.
▸Parent of i at floor((i-1)/2), children at 2i+1 and 2i+2. No pointers, so the same memory is a tree and a backing array.

That still does not find "A" in O(1). The heap is ordered by fireTime, not by id. The second structure is indexById: Map<string, number> — id to current heap index.

For this design, Map.get is commonly treated as average O(1). The JavaScript specification requires Map access to be sublinear on average, but it does not promise a particular hash-table implementation or a strict worst-case O(1) bound.

The lockstep rule: every swap of two heap slots must patch both map entries. If you swap the objects and forget the map, the next cancel walks to a stale index, mutates the wrong timer, and the heap property silently dies. Watch a swap in the visualizer: the tree, the array cells, and the indexById chips all move together.

edit uses that index, then compares the new fireTime to the old one:

▸Smaller fireTime → the timer is more urgent → siftUp.
▸Larger fireTime → less urgent → siftDown.
▸Equal → leave it.

newDelay is not “add this many units to the old fireTime.” It is currentTime + newDelay. If virtual time is already 4 and you pass newDelay = 2, the timer is due at 6, even if it used to be due at 10.

Equal fireTimes need a clear product rule. This lab chooses stable insertion order: a monotonic sequence makes comesBefore a total order. Earlier fireTime wins; if tied, smaller sequence wins. That is why A, B, and C at delay 5 fire A then B then C. Another service could choose a different tie-break if its requirements differ.

Complexity

Method	Time
`add`	O(log n)
`cancel`	average O(1) lookup + O(log n) repair
`edit`	average O(1) lookup + O(log n) repair
`advance` (k timers fire)	O(k log n)
id lookup	average O(1) for this design
space	O(n) for the heap plus O(n) for the map

advance is not O(log n). Each fired timer is a removeAt(0), which is O(log n). If 50 timers share the same deadline, you pay 50 repairs. That is the honest bound.

Important invariants

The status chip on the heap header expands to four checks. A public operation must finish with all four checks passing. While the visualizer is showing an intermediate mutation, it reports Operation in progress instead of treating the temporary state as a completed failure.

▸The root is the earliest timer. Nothing in the heap comesBefore index 0.
▸Every indexById entry points at the matching heap slot, and every heap timer is in the map. Sizes match. No dangling index.
▸Equal firing times are ordered by sequence along every parent–child edge (the heap property, including the tie-break).
▸No remaining timer is overdue. Every fireTime is ≥ current virtual time. A timer with delay = 0 is due at now; advance(0) is what actually fires it.

If a completed operation breaks a rule, the chip switches to Invariant failed and expands to name the broken rule. The label changes as well as the colour.

Alternative designs

Design	What it wins	What it loses
Sorted array	Easy to explain	O(n) insert/cancel
Min-heap, scan by id	Simpler code	O(n) cancel/edit
Heap + `indexById` (this lab)	O(log n) for all four ops	You must patch the map on every swap
Balanced search tree keyed by `(fireTime, sequence)` plus id map	Ordered iteration	More complex implementation; still two structures
Timing wheel	Efficient when deadlines fit known time ranges	More involved buckets and edge cases
Delay queue in Redis / BullMQ	Persistence, retries and workers	Adds an operational layer beyond this in-memory scheduler

Testing strategy

Good tests verify more than the final fired timer. They also check the state that makes scheduling bugs visible:

▸After every public operation, run the four invariants.
▸After every swap, check that both ids in indexById match the objects now sitting at those indices.
▸Equal deadlines: insert A, B, C at the same delay; advance must return them in insertion order.
▸edit upward and downward: the timer must leave its old slot and the new root must be the true minimum.
▸removeAt on root, middle, and last index — last index is the easy path (no hole to fill); middle is where a wrong map patch shows up.
▸Reject empty ids, duplicate ids, negative delays, and NaN.
▸Cross-check against a sorted-array reference model: generate random add/cancel/edit/advance sequences; both implementations must fire the same ids in the same order.

If the visualizer and the reference model disagree, inspect both implementations. The reference model is easier to reason about, but it can still contain a bug.

How this connects to Agent Telar

Agent Telar uses BullMQ for background jobs. This lab isolates the scheduling problem so you can see why a queue needs fast deadline ordering and reliable job lookup. BullMQ provides the wider operational layer, including persistence, retries and workers; it does not use this exact TimeService class.

See the production queue code in Phase 5 on GitHub.

Suggested learner exercises

▸Load Edit a timer so it moves upward. Step until A swaps with B. Pause. Write down indexById before and after the swap without looking at the chips, then reveal them.
▸Load Fire multiple timers with equal times. Predict the fired list before you press Play.
▸At virtual time 4, edit("A", 2) — compute the new fireTime on paper (currentTime + newDelay). Confirm it is not oldFireTime - something.
▸Implement comesBefore without sequence. Run the equal-times scenario. Notice the order can depend on how siftDown picks children. Put sequence back.
▸Add a fifth operation, peek(): Timer | undefined, that must be O(1) and must not mutate the heap. Where does it read?

The problem and four operations