BinaryHeap's Sorted Vector Order Is the Opposite of Pop Order

Rust's BinaryHeap is a max-heap by default. pop returns the greatest element first. However, into_sorted_vec consumes the heap and returns an ascending vector. The failing fixture compares these two outputs and shows that their directions are opposite.

Priority order and sorted storage order are different APIs

BinaryHeap::pop removes the greatest item. Repeating it gives descending priority order for ordinary ascending Ord values.

BinaryHeap::into_sorted_vec instead promises a vector sorted in ascending order. It consumes the heap and arranges the complete output for callers that want a conventional sorted sequence.

Neither direction is surprising after reading each contract, but it is easy to infer one from the other. I name result variables ascending and priority_order instead of both being sorted.

Iteration is not priority traversal

The heap's iter visits elements in an arbitrary order. A heap maintains only the partial ordering needed to expose its greatest element efficiently. Its internal array is not a fully sorted list.

This matters in logging, serialization, snapshots, and tests. Iterating a heap may produce output that looks nearly ordered for one input and changes with another implementation or mutation history. I do not publish that order as an API.

If I need non-destructive ordered output, I can clone the heap when elements are cloneable and consume the clone, or collect references and sort them. That cost should be visible because the data structure was chosen for priority access, not free total ordering.

Min-heaps reverse the element ordering

Wrapping values in Reverse<T> turns the default max-heap into min-priority behaviour. Then pop yields the smallest underlying value first. The sorted-vector ordering is defined for the wrapper's Ord, which can make the rendered underlying direction look reversed again.

Custom task types can implement Ord so urgency, deadline, and tie-break IDs form one total order. I keep Eq and Ord consistent because the collection relies on them. Changing fields that influence ordering while an item is inside the heap is a logic error even if interior mutability makes it possible.

The direction belongs to the comparator, not a visual assumption about numbers.

Equal priorities need deliberate tie-breaking

Several jobs may have the same primary priority. A heap does not provide stable insertion ordering for equal elements. If FIFO behaviour within a priority is required, I include a monotonic sequence number in the ordering, with the correct direction.

This becomes important for reproducibility and fairness. A test that accepts any tied order may be correct for a pure priority queue, while a user-facing scheduler may require a stable documented tie rule.

I avoid using wall-clock timestamps alone as unique tie breakers. Equal resolution, clock adjustment, and distributed clocks make them weaker than a local sequence or explicit ID.

Choose output from consumer needs

For an online scheduler, repeatedly peeking and popping is natural. For a report that needs ascending values, into_sorted_vec is direct. For top-k processing, there may be no reason to sort every remaining item.

The repaired fixture asserts the two contracts separately: ascending vector output and descending pop output. It does not force one API to imitate the other.

Complexity also matters. Building, pushing, popping, and total conversion have different costs. I use the standard documentation and a representative benchmark when scale is relevant, while keeping ordering assertions independent of timing.

My heap-order checklist

• Is the consumer asking for greatest-first priority or ascending sorted output?
• Is ordinary iteration accidentally exposed as ordered?
• Does Reverse or a custom Ord change the visible direction?
• Are equal priorities given a deliberate tie-break rule?
• Can ordering fields mutate while an item is in the heap?
• Must ordered inspection preserve the original heap?
• Would top-k processing avoid sorting every value?
• Do tests name and assert each ordering contract separately?

The core principle is that a partial-order data structure can expose several meaningful traversals. BinaryHeap optimises access to one extreme; it does not make every view priority-ordered. I choose pop order, sorted conversion, or arbitrary inspection according to the consumer's real contract.