heapq: a priority queue that is FIFO among equal priorities

Build a priority queue on heapq with stable tie-breaking and cancellation.

class TaskQueue:
    def __init__(self) -> None: ...
    def push(self, priority: int, name: str) -> None: ...
    def remove(self, name: str) -> None: ...     # KeyError if not queued
    def pop(self) -> str: ...                    # IndexError when empty
    def __len__(self) -> int: ...                # number of live tasks


def solve(ops: list[list[object]]) -> list[object]: ...

Lower priority numbers come out first. Among equal priorities, the earliest pushed comes out first. Task names are unique.

solve replays a script of operations and collects results:

The tuple trap is the whole problem. heappush(heap, (priority, name)) works perfectly until two items share a priority. Tuples compare element by element: with distinct priorities the comparison stops at the first element and the payload is never examined. The moment there is a tie, Python falls through to comparing the payloads — and because these payloads are strings and therefore orderable, it does not raise. It silently orders alphabetically, so your FIFO queue becomes an alphabetical one. (With unorderable payloads it raises TypeError instead, which is the luckier outcome.) One of the tests pushes zebra, apple and mango at the same priority; the naive heap returns them in the wrong order and never errors.

The documented fix is a monotonic counter as the tiebreaker, and the typed expression of it is:

@dataclass(order=True, slots=True)
class _Entry:
    priority: int
    sequence: int
    name: str = field(compare=False)

order=True compares the fields as a tuple in declaration order; field(compare=False) says “tie-break on nothing further” precisely and self-documentingly, which a bare tuple does not.

Cancellation is lazy deletion. heapq has no remove, because removing an arbitrary element is $O(n)$ to find plus a full heapify to repair. Record the cancellation in a set and skip cancelled entries as they surface at the top. Discard the name from that set once its entry has been dropped, or the set is the same leak in a different container.

Worth knowing but not tested: 3.14 adds heapify_max / heappush_max / heappop_max, so a max-heap no longer needs the negate-the-priority trick.