Why BinaryHeap::into_sorted_vec Returns Ascending Order

Rust's BinaryHeap is a max-heap. peek and pop expose the greatest value. From that fact I once assumed every consuming operation would produce greatest-first order.

The failing program converts a heap containing 4, 1, 3, 2 with into_sorted_vec. The result is [1, 2, 3, 4], not [4, 3, 2, 1].

There is no contradiction. Priority order and the final representation chosen by a sorting conversion are two different contracts.

The conversion promises ascending order

BinaryHeap::into_sorted_vec consumes the heap and returns a vector in sorted ascending order. It uses the heap to perform an in-place heap sort.

A max-heap places its maximum at the root. During heap sort, moving successive maxima into the high end of the vector naturally leaves the final vector ascending from low index to high index.

The name says “sorted,” and Rust follows the ordinary collection convention that an unqualified sorted sequence is ascending. It does not say “heap pop order.”

The repaired program verifies both valid results on identical inputs: into_sorted_vec gives ascending order, while repeated pop calls give descending priority order.

Use pop when the priority queue is the abstraction

BinaryHeap::pop removes the greatest item. Repeating it is the stable API for max-priority order:

let ordered = std::iter::from_fn(|| heap.pop()).collect::<Vec<_>>();

This destroys the heap, just like into_sorted_vec, but the output order is greatest first. It also lets me stop after the first k priorities without sorting and returning every value.

When I only need the best item, peek avoids removal. When I need all values ascending for storage, display, or binary search, the vector conversion already gives the appropriate order.

Choosing the API from the consumer's need is clearer than converting and immediately calling reverse without explaining why.

Ordinary iteration is not either sorted order

The consuming BinaryHeap::into_iter visits the underlying representation in arbitrary order. Borrowed iter has the same important warning.

The root is greatest, but the remaining array only satisfies the heap invariant: every parent is at least as large as its children. Siblings and separate subtrees are not globally sorted.

For example, a valid internal sequence might begin with the maximum and then contain values that look almost sorted for one input. That is an accident of construction. Tests that use three conveniently ordered integers can strengthen the wrong mental model.

I use data whose heap storage is unlikely to look globally ordered, and I call an API that explicitly promises the order I need.

Duplicate priorities need another rule

Ascending or descending order does not decide the relative order of items that compare equal. A binary heap is not a stable queue for equal priorities.

If FIFO behaviour among equal priorities matters, I include a sequence number in the ordered key. The ordering implementation can compare priority first and reverse or preserve the sequence according to the product rule.

I do not rely on current internal positions. Even if one build appears stable, pushes, pops, allocator changes, and standard-library improvements can rearrange equal elements.

This matters for job schedulers. “Same priority” is not enough to specify fairness.

Reverse changes which item is greatest to the heap

Rust provides a max-heap, but BinaryHeap<Reverse<T>> acts like a min-priority queue. In that wrapper, pop yields the smallest underlying T first because Reverse changes its ordering.

The word “ascending” for into_sorted_vec then applies to the wrapped Reverse<T> values. After unwrapping, the apparent order of T can look reversed. I state which type's Ord implementation is being discussed whenever wrappers or custom entries are involved.

Custom Ord is part of the data structure. Mutating a field that affects ordering while an item is inside the heap is a logic error, covered separately by RFA-133.

A good test compares operations, not internals

The evidence creates two heaps from the same values. One is converted; the other is popped. This isolates the API contract from insertion history.

I avoid checking as_slice or debug output as proof of priority order. Those reveal representation, not the sequence promised by future removals.

When output direction is wrong, my checks are short: identify the Ord type, determine whether the consumer wants ascending storage or priority order, check for Reverse, avoid ordinary iteration, and define a tie-breaker when equal priorities matter.

The core principle is that one data structure can expose several orderings for different jobs. BinaryHeap maintains enough order to find the maximum efficiently. pop follows that priority. into_sorted_vec finishes a full sort and deliberately returns the conventional ascending sequence.