A daemon calls heap.Fix after re-prioritising a queued job, yet the wrong jobs fire. What went wrong?

seniornice to knowfreq 26%

answer

the package remembers nothing about elements
Fix takes a number, not a job
who writes that number down
Swap moves things and must say so
stale after the very first sift

basics

~20 s

container/heap tracks no positions, so heap.Fix trusts the index you pass it. If Swap does not write each element's new position into its index field, that field goes stale after the first sift and Fix repairs the wrong slot.

solid answer

~50 s

heap.Fix(h, i) takes an index, not an element — the package keeps no map from item to position, so the only way to know where a job currently sits is a field on the job that your Swap maintains. The classic bug is a Swap that exchanges the two elements but forgets q[i].index = i; q[j].index = j. Every element's index is correct until the first sift, then permanently wrong, and heap.Fix(&q, job.index) re-sifts some unrelated element while the re-prioritised one stays out of order. heap.Remove breaks the same way. Nothing panics, because the slice is still a valid slice; the queue just stops returning the earliest deadline. I would prove it with a test helper that walks the queue after every operation asserting both q[i].index == i and that no child is Less than its parent, then run the daemon's whole schedule through it.

`heap.Fix(h, i)` takes an index, not an element — the package keeps no map from item to position, so the only way to know where a job currently sits is a field on the job that *your* `Swap` maintains. The classic bug is a `Swap` that exchanges the two elements but forgets `q[i].index = i; q[j].index = j`. Every element's index is correct until the first sift, then permanently wrong, and `heap.Fix(&q, job.index)` re-sifts some unrelated element while the re-prioritised one stays out of order. `heap.Remove` breaks the same way. Nothing panics, because the slice is still a valid slice; the queue just stops returning the earliest deadline. I would prove it with a test helper that walks the queue after every operation asserting both `q[i].index == i` and that no child is `Less` than its parent, then run the daemon's whole schedule through it.

code

go · 10 lines

func (q JobQueue) Swap(i, j int) {
	q[i], q[j] = q[j], q[i]
	q[i].index = i // omit these two and every index goes
	q[j].index = j // stale after the first sift
}

func (s *Scheduler) Reschedule(job *Job, at time.Time) {
	job.Deadline = at
	heap.Fix(&s.queue, job.index)
}

go deeper

for a junior

Recall that heap.Fix needs the element's current index and that container/heap does not track it for you. Knowing the index lives in a field on the element is the takeaway.

for a middle

Explain the mechanism end to end: Push seeds the index, Swap rewrites it on every exchange, Pop invalidates it, and Fix consumes it. Say why the bug is silent rather than a panic.

for a senior

Demonstrate the diagnosis. Describe the invariant walk asserting index equality and no child outranking its parent, run after every operation in a randomised test, and note that the bug hides in small queues where no sift occurs.

for a principal

Own the design call. Decide whether elements carry a mutable index at all, or whether lazy deletion with cancelled entries buys enough safety to justify the extra memory, and be explicit that the index field forbids one element living in two queues.

Why an index field exists at all

container/heap is deliberately stateless about your elements. It gets Len, Less and Swap, and that is the entire window it has onto your data. It cannot hand you a handle, it cannot look an element up, and it has nowhere to store a position map. So when you need to re-prioritise something that is already in the queue — bump a job's deadline, cancel it, raise its priority — the package can only offer index-taking operations:

heap.Fix(h, i) — the element at i changed value; restore ordering, O(log n).
heap.Remove(h, i) — pull the element at i out of the middle, O(log n).

Which leaves you with the question the package refuses to answer: what is i? The answer has to be a field on the element, kept current by the one method that ever moves elements — Swap.

func (q JobQueue) Swap(i, j int) {
    q[i], q[j] = q[j], q[i]
    q[i].index = i
    q[j].index = j
}

Those two extra lines are the entire mechanism, and forgetting them is the failure. Push must seed the field (job.index = len(*q)) and Pop conventionally invalidates it (job.index = -1) so a reused handle is obviously wrong rather than plausibly wrong.

How the failure actually presents

A delayed-job scheduler holds []*Job ordered by Deadline. An operator reschedules a job:

func (s *Scheduler) Reschedule(job *Job, at time.Time) {
    job.Deadline = at
    heap.Fix(&s.queue, job.index)
}

With a Swap that maintains index, this is correct and cheap. Without it, job.index still holds wherever the job was when it was pushed. heap.Fix dutifully sifts that slot — some other job — while the rescheduled job sits in the wrong place. From there:

The heap invariant is broken, so heap.Pop can return a job whose deadline has not arrived while a due one stays buried.
The daemon's "sleep until q[0].Deadline" loop wakes at the wrong time.
There is no panic, no error return, no go vet finding. The slice is a perfectly valid slice.
It is load-dependent: with two or three jobs no sift ever happens, so tests pass and production does not.

Also note the second half of Reschedule. Mutating job.Deadline while the job is in the heap is what makes Fix necessary. If someone changes a field that Less reads and never calls Fix or heap.Init, the queue is wrong from that moment even if every index is perfect.

The diagnostic

Do not reason about it; assert it. A test helper that walks the whole queue after every operation catches both halves of the bug in one pass:

Position check: q[i].index == i for every i. This fails the instant Swap forgets its two lines.
Invariant check: for every i > 0, !q.Less(i, (i-1)/2) — no child outranks its parent. This fails when Fix was skipped or applied to the wrong slot.

Drive it from a test that pushes, pops, reschedules and removes in a randomised sequence, checking after each step. The point of checking after every step rather than at the end is that the first failing operation is named, instead of a corrupted queue reported ten operations downstream.

Design consequences worth stating

Once elements carry a mutable index, three things become true and are worth saying out loud to whoever owns the code:

An element may live in exactly one heap. A single index field cannot describe two positions, so a *Job in two queues corrupts both.
The element type is no longer inert. index is unexported and meaningless outside the queue package, so the queue and the element type should live together and the field should never be set by callers.
Concurrency is yours to add. container/heap has no locking whatsoever. A scheduler goroutine and an HTTP handler that reschedules must serialise every heap operation and every mutation of a field Less reads, under the same mutex — the read of job.index inside Reschedule is part of the critical section, not something you can do before taking the lock.

A reasonable alternative when re-prioritisation is rare: drop the index field, mark the old entry cancelled, and push a fresh entry, skipping stale ones as they pop. That trades memory and a lazy-deletion check for removing an entire class of silent corruption — a good trade for a team that will not otherwise write the invariant test.

## Why an index field exists at all `container/heap` is deliberately stateless about your elements. It gets `Len`, `Less` and `Swap`, and that is the entire window it has onto your data. It cannot hand you a handle, it cannot look an element up, and it has nowhere to store a position map. So when you need to re-prioritise something that is *already* in the queue — bump a job's deadline, cancel it, raise its priority — the package can only offer index-taking operations: - `heap.Fix(h, i)` — the element at `i` changed value; restore ordering, O(log n). - `heap.Remove(h, i)` — pull the element at `i` out of the middle, O(log n). Which leaves you with the question the package refuses to answer: *what is i?* The answer has to be a field on the element, kept current by the one method that ever moves elements — `Swap`. ``` func (q JobQueue) Swap(i, j int) { q[i], q[j] = q[j], q[i] q[i].index = i q[j].index = j } ``` Those two extra lines are the entire mechanism, and forgetting them is the failure. `Push` must seed the field (`job.index = len(*q)`) and `Pop` conventionally invalidates it (`job.index = -1`) so a reused handle is obviously wrong rather than plausibly wrong. ## How the failure actually presents A delayed-job scheduler holds `[]*Job` ordered by `Deadline`. An operator reschedules a job: ``` func (s *Scheduler) Reschedule(job *Job, at time.Time) { job.Deadline = at heap.Fix(&s.queue, job.index) } ``` With a `Swap` that maintains `index`, this is correct and cheap. Without it, `job.index` still holds wherever the job was when it was pushed. `heap.Fix` dutifully sifts *that* slot — some other job — while the rescheduled job sits in the wrong place. From there: - The heap invariant is broken, so `heap.Pop` can return a job whose deadline has not arrived while a due one stays buried. - The daemon's "sleep until `q[0].Deadline`" loop wakes at the wrong time. - There is no panic, no error return, no `go vet` finding. The slice is a perfectly valid slice. - It is load-dependent: with two or three jobs no sift ever happens, so tests pass and production does not. Also note the second half of `Reschedule`. Mutating `job.Deadline` **while the job is in the heap** is what makes `Fix` necessary. If someone changes a field that `Less` reads and never calls `Fix` or `heap.Init`, the queue is wrong from that moment even if every index is perfect. ## The diagnostic Do not reason about it; assert it. A test helper that walks the whole queue after every operation catches both halves of the bug in one pass: - **Position check**: `q[i].index == i` for every `i`. This fails the instant `Swap` forgets its two lines. - **Invariant check**: for every `i > 0`, `!q.Less(i, (i-1)/2)` — no child outranks its parent. This fails when `Fix` was skipped or applied to the wrong slot. Drive it from a test that pushes, pops, reschedules and removes in a randomised sequence, checking after each step. The point of checking *after every step* rather than at the end is that the first failing operation is named, instead of a corrupted queue reported ten operations downstream. ## Design consequences worth stating Once elements carry a mutable `index`, three things become true and are worth saying out loud to whoever owns the code: 1. **An element may live in exactly one heap.** A single `index` field cannot describe two positions, so a `*Job` in two queues corrupts both. 2. **The element type is no longer inert.** `index` is unexported and meaningless outside the queue package, so the queue and the element type should live together and the field should never be set by callers. 3. **Concurrency is yours to add.** `container/heap` has no locking whatsoever. A scheduler goroutine and an HTTP handler that reschedules must serialise every heap operation *and* every mutation of a field `Less` reads, under the same mutex — the read of `job.index` inside `Reschedule` is part of the critical section, not something you can do before taking the lock. A reasonable alternative when re-prioritisation is rare: drop the index field, mark the old entry cancelled, and push a fresh entry, skipping stale ones as they pop. That trades memory and a lazy-deletion check for removing an entire class of silent corruption — a good trade for a team that will not otherwise write the invariant test.

What else breaks once the index field is stale?
`heap.Remove(&q, job.index)` deletes an unrelated element and leaves the intended one queued — worse than Fix, because the queue also loses a job. The `index = -1` sentinel that `Pop` conventionally writes stops being trustworthy too, so a handle to an already-popped job no longer looks obviously invalid.
Is it ever acceptable to change a queued job's deadline without calling heap.Fix?
Only if you re-establish the invariant another way, such as calling `heap.Init` afterwards, which is O(n) rather than O(log n). Otherwise the element is out of order from that moment: `heap.Pop` may keep returning non-minima indefinitely, and nothing in the package will notice or complain.
Why call heap.Fix rather than heap.Remove followed by heap.Push?
They give the same result, but Fix is cheaper — it sifts once from position `i` in whichever direction the new value demands, while Remove plus Push is two full O(log n) operations plus the churn of detaching and re-appending. The package documents Fix as the equivalent, less expensive alternative.
How would you make this design safe for a handler goroutine that reschedules?
Serialise everything the heap can observe under one mutex: the `heap.*` calls, the read of `job.index`, and the write to `job.Deadline`, since `Less` reads that field during a sift. Better still, keep the queue owned by the scheduler goroutine and have handlers send reschedule requests over a channel, so no lock discipline has to be remembered.

Fix is a courier told to fetch the parcel from shelf seven. If the warehouse reshuffles shelves without updating the manifest, the courier still goes to shelf seven and confidently returns the wrong parcel.

saying these in an interview costs you the question

Assumes container/heap tracks each element's position
Updates the index in Push but not in Swap
Mutates a queued job's priority without calling heap.Fix
Expects a broken heap invariant to panic
Puts the same element pointer into two heaps
Reads job.index outside the mutex that guards the queue

A daemon calls heap.Fix after re-prioritising a queued job, yet the wrong jobs fire. What went wrong?

§ answer

basics

solid answer

code

§ go deeper

▾level notes4 levels

▾deep dive~4 min

Why an index field exists at all

How the failure actually presents

The diagnostic

Design consequences worth stating

▾common follow-ups4 questions

▾analogy~10 s

▾red flags6 flags

Why an index field exists at all

How the failure actually presents

The diagnostic

Design consequences worth stating

answer

go deeper