A standard-library priority queue only pops the smallest key, but your scheduler must serve the highest priority first. What are your options?

## Orientation is a property of the queue, not of the items A priority queue answers exactly one question: of everything I am holding, which item is most important? "Most important" is not intrinsic to the items — it is whatever ordering rule the queue was given. Standard-library priority queues bake that rule in when the queue is created, and each library picks a default: either the smallest key comes out first (min-oriented) or the largest does (max-oriented). Nothing in the underlying binary heap forces one direction. A heap is just a nearly-complete tree in which every parent compares favourably against its children; flip the meaning of "favourably" and a min-heap becomes a max-heap with no other change to the code, the layout, or the costs. Insert stays O(log n), extract-top stays O(log n), inspecting the top stays O(1), and building from an existing collection bottom-up stays O(n). ## The concrete mismatch Take a quality-of-service packet scheduler. Each queued packet carries a numeric priority field where a **larger** number means "send this sooner": control traffic 7, voice 5, bulk transfer 0. The queue you have pops the **smallest** key. Three ways to reconcile them: | Option | Works for | What it costs you | |---|---|---| | Reversed comparison function at construction | any key type | one small function; the ordering rule is stated once, in one place | | Negated numeric keys on insert | numeric keys only | every read site must un-negate; stored values, logs and dumps are sign-flipped | | Drain the queue and reverse the output | offline batches only | needs all items up front, O(n log n), and destroys the streaming property | ### Option 1 — reverse the comparison You supply the ordering rule the queue uses to decide which of two entries wins. Reversing it (compare `b` against `a` instead of `a` against `b`) makes the largest priority the one that surfaces. The stored packets are untouched: a packet with priority 7 still reads as 7 everywhere. This composes with any key — numbers, timestamps, version identifiers, multi-field records — and it puts the scheduler's policy in exactly one readable place. ### Option 2 — negate the key Push `-7` instead of `7` and a min-oriented queue serves control traffic first. The arithmetic is sound and it is a genuinely popular trick, especially where the library's ordering rule is awkward to supply. The price is that the negation is now part of a **contract spread across the code**: the insert site negates, the extraction site un-negates, the metrics exporter had better un-negate, and the log line that prints "priority -7" will confuse whoever is on call. It also does not generalise: an opaque record or a composite key has no negation. ### Option 3 — drain and reverse Extract everything into a list and reverse it. This is not an inversion of the queue at all; it is a sort. It requires the full input before you can serve anything, which is precisely what a priority queue exists to avoid — a scheduler must serve the best item available *now*, while new packets keep arriving. ## Things that do not work - **Flipping a live queue's orientation.** The ordering rule is fixed at construction, and the existing arrangement already satisfies the old rule. To change the rule you build a new queue from the same items — which is O(n) with a bottom-up build, so it is cheap, but it is a rebuild, not a toggle. - **Reading or sorting the backing storage.** Heap order is a partial order; only the top position is guaranteed. - **Assuming reversal changes complexity.** It changes which item is at the top and nothing else. ## Libraries genuinely disagree here This is one of the places where mainstream runtimes made opposite calls on the same concept: Python's standard heap functions are min-oriented, while C++'s standard priority queue is max-oriented by default. Neither is more correct; the lesson is that orientation is a *library default*, not a mathematical fact, so the first thing to check when you pick up an unfamiliar priority queue is which end it serves from. ## The rule of thumb Use a reversed comparison function unless the key is numeric, small, and you control every place it is read — then negation is an acceptable shortcut. Whichever you pick, state it once, near the construction of the queue, so the next reader does not have to infer the scheduler's policy from a minus sign.