In a priority queue, what order do two equal-priority items come out in, and can you rely on it?

## What the contract actually says `extract-top()` returns **an** item of top priority. Not the earliest such item, not the latest — an item. When exactly one item holds the top priority the wording does not matter. When several tie, that one indefinite article is the whole story: the abstraction refuses to choose, and any behaviour you observe is a fact about the implementation and the operation history, not a promise. This surprises people because the thing is called a queue, and queues are the container people associate with fairness. A support desk hits it immediately: two tier-2 tickets are filed ten minutes apart, and the older one is dispatched second. Nothing is broken; the guarantee was never made. ## Why a heap-backed queue actively scrambles ties With a binary heap behind the queue, the reordering is mechanical. On insert, the new element goes at the end of the array and sifts **up**, swapping with its parent while it outranks it — a tied parent is not outranked, so the newcomer stops beneath it, sometimes. On extract, the last element in the array is moved to the root and sifts **down**, swapping with the better of its two children — and when children tie, which one is chosen is an implementation decision inside that comparison. So the position of a tied element after k operations is a function of every insert and extract that happened before it, and of the array size at each of those moments. Two consequences worth stating out loud in an interview: - The tie order is **not reproducible in any useful sense**. The same multiset of items, inserted in the same order but with extractions interleaved differently, drains differently. - It is **not stable across versions**. A library that changes which child it prefers on a tie, or that changes its growth strategy, changes your dispatch order without changing any documented behaviour. Trace the fragment above: T3 is guaranteed first because tier 1 beats tier 2 outright. The remaining three tie, and where each lands depends on the sift path taken when T3 was removed. ## The fix: make ties impossible The robust answer is never "find an implementation that happens to be fair". It is to extend the ordering rule so no two entries compare equal: ``` seq = 0 enqueue(pq, ticket): seq = seq + 1 insert(pq, {key: (ticket.tier, seq), value: ticket}) better(a, b) = a.key.tier < b.key.tier or (a.key.tier == b.key.tier and a.key.seq < b.key.seq) ``` The counter increments on every enqueue and never repeats, so the composite key is a **strict total order**: for any two distinct entries, exactly one comes first, and the implementation has no freedom left to exercise. Among equal tiers you now get arrival order by construction. Want most-recent-first among equals instead? Compare the counter the other way. The policy became explicit and testable instead of emergent. Costs: one integer per entry, and one extra field comparison inside a comparison that already runs O(log n) times per operation. Asymptotics are unchanged — peek stays O(1), insert and extract stay O(log n). ## Two traps around the tie-breaker itself **Do not tie-break on a wall-clock creation time.** It looks like the natural key and fails three ways: its resolution is coarse enough that simultaneous arrivals still tie, it can move backwards when the clock is adjusted, and when several producers feed one queue their clocks disagree. A single monotonically increasing counter owned by the enqueue path has none of these problems. If the queue is fed from several producers, the counter has to be shared and monotone across them, which is a real design constraint worth naming. **A tie-breaker is only meaningful when the tied items are distinguishable.** If two entries are genuinely interchangeable — the same value with no identity — then the order they emerge in cannot be observed and there is nothing to fix. Support tickets have identity, so the order is very much observable, by the person waiting on the older one. ## What to say when asked Name the contract wording first (an item of top priority, not a specific one), then the mechanism (sift-up and sift-down move tied elements past each other, so the order depends on operation history), then the fix (composite key with a monotone counter, which removes ties instead of hoping about them), and finish with the cost (one field, no change in asymptotics). Candidates who jump straight to the fix without the contract usually cannot say why it works.