Build a Task Queue That Keeps Arrival Order for Ties

A job runner needs a queue that hands out the most urgent task first. Tasks with the same priority must come out in the order you added them, and the caller can cancel a task while it waits. Build the queue on heapq.

queue = TaskQueue()
queue.push(2, "zebra")
queue.push(2, "apple")
queue.push(1, "urgent")
queue.remove("urgent")
len(queue)   # 2
queue.pop()  # "zebra", because it was added before "apple"
queue.pop()  # "apple"
queue.pop()  # raises IndexError

What to write

class TaskQueue:
    def __init__(self) -> None: ...
    def push(self, priority: int, name: str) -> None: ...
    def remove(self, name: str) -> None: ...
    def pop(self) -> str: ...
    def __len__(self) -> int: ...

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

TaskQueue follows these rules:

• A lower priority number comes out first. Priorities can be negative.
• Among tasks with equal priority, pop returns the one pushed first.
• remove(name) cancels a waiting task, and len(queue) drops by one at once. It raises KeyError for a name that was never pushed, was already cancelled or was already popped.
• pop() removes and returns the name of the next live task. It raises IndexError when no live task remains, even if cancelled entries are still in the heap.
• len(queue) counts live tasks, not the entries stored in the heap.
• The methods raise these exceptions themselves. Only solve turns them into strings.

Keep a sequence number that goes up on every push, and order entries by priority and then by sequence. Do not use (priority, name) as the heap entry, because that breaks ties alphabetically. The dataclass from the article does the job:

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

Import dataclass and field from dataclasses.

To cancel a task, keep a set of live names and a set of cancelled names, and leave the cancelled entry in the heap. In pop, take entries off the heap until you find a live one, and return its name. For each cancelled entry you skip, remove its name from the cancelled set. If only cancelled entries remain, pop throws them all away and raises IndexError. This lazy deletion works because every name is unique across all the pushes in one run, so a name never comes back.

solve(ops) starts with a new queue, runs each operation in order, and returns a list of results:

Edge cases

• An empty list of operations returns [].
• Cancelling a task a second time raises KeyError, even while its old entry is still in the heap.
• Leave the ops list unchanged.