Why can heapq.heappush raise TypeError when two entry tuples tie on priority?

### heapq only knows `<` The module has no `key=` parameter and no comparator hook. Every ordering decision it makes is a single `a < b` between two elements of the list, delegated to those objects' own rich-comparison methods. That is why the universal idiom for a priority queue in Python is to push *tuples* whose first field is the priority: tuple comparison does the right thing for free. But tuple comparison does more than most people picture. `tuple.__lt__` walks the fields left to right, and the moment it finds a pair that is unequal it returns that result. If field 0 of both tuples compares equal, it moves to field 1 and compares **those**. So the payload you attached purely as cargo becomes part of the ordering the first time two priorities collide. ```python (1, {"id": "a"}) < (2, {"id": "b"}) # False, decided at field 0 (2, {"id": "a"}) < (2, {"id": "b"}) # TypeError, falls through to the dicts ``` Dicts define `==` but not `<`. Sets define `<` as the subset relation, which is a partial order — arguably worse, because it does not raise; it just yields an ordering that is neither total nor meaningful. Ordinary user classes without `__lt__` raise. Every one of these is a bug that only appears when two priorities happen to be equal. ### Why this is a production-shaped failure Consider a nightly genome-annotation run that queues per-region jobs by priority and executes them from a heap. In a small test fixture, priorities are distinct, the comparison never reaches field 1, and everything passes. On the real corpus, two regions eventually score identically — and the six-hour run dies with a `TypeError` from deep inside `heapq.heappush`, hours in, with a traceback that names the module rather than your data. It is a latent bug measured in wasted machine-hours. ### The counter idiom The stdlib's own priority-queue notes prescribe a monotonically increasing tiebreak field: ```python import heapq from itertools import count tiebreak = count() queue = [] heapq.heappush(queue, (priority, next(tiebreak), payload)) ``` `itertools.count()` hands out `0, 1, 2, ...`. Because every entry gets a distinct integer, no two tuples are ever equal through field 1, so tuple comparison stops there and the payload is never touched — it can be a dict, an un-orderable object, `None`, anything. As a bonus you get a guarantee the heap itself does not offer: among equal priorities, the entry pushed first has the smaller counter and therefore pops first. That is FIFO within a priority band, and it is deterministic, which matters for reproducible pipeline runs. Two things people reach for instead, and why they are worse. A random float as the tiebreak makes ordering nondeterministic between runs and can, in principle, collide. `id(payload)` is unique but arbitrary, address-reuse-prone, and produces an order nobody can reason about. ### When the payload should participate Sometimes you *want* a secondary ordering — same priority, then earliest deadline. Then put that field in the tuple explicitly, before the counter: `(priority, deadline, next(tiebreak), payload)`. Making the order visible in the tuple is the whole point; relying on an accidental fall-through to the payload is what got you the `TypeError`. If positional tuples are getting unwieldy, a dataclass says the same thing with names: ```python from dataclasses import dataclass, field from typing import Any @dataclass(order=True) class Entry: priority: int sequence: int payload: Any = field(compare=False) ``` `order=True` generates `__lt__` from the fields in declaration order, and `compare=False` excludes `payload` from it, which is exactly the invariant the counter idiom enforces by construction. ### Removing an entry The related question interviewers often tack on: you cannot delete from the middle of a heap. The stdlib recipe keeps a dict from key to entry, mutates the entry's payload slot to a removed-sentinel instead of deleting it, and skips sentinels when popping — lazy deletion. Note that this only works because the entry is a mutable object reachable from outside the list; a tuple entry cannot be edited in place, so the recipe uses a list as the entry.