BinaryHeap::iter Is Not Priority Order

I inspected a BinaryHeap with iter() and saw the maximum first. I then treated the rest as a descending queue. With values one through four, the underlying visit order was not 4, 3, 2, 1.

The failing program collects the iterator and asserts descending priority. The pinned fixture exposes heap representation order instead.

A heap is partially ordered

A max binary heap maintains a parent-versus-child invariant. Every parent is at least as large as its children, which puts a maximum at the root. It does not compare and order every pair of nodes.

This weaker invariant is why insertion and maximum removal can be efficient. Maintaining a fully sorted vector after every insertion would have a different cost profile.

BinaryHeap::iter explicitly visits the underlying vector in arbitrary order. The word arbitrary is the contract. The exact vector observed in Rust 1.98.1 is evidence for the failure, not a format that application code may depend upon.

Repeated pop is the priority-queue operation

BinaryHeap::pop removes the current greatest value, repairs the heap, and repeats that guarantee for the next call. A loop over pop produces descending priority for a max heap.

It also consumes the heap's contents. If I need to preserve the original and T: Clone, I can clone the heap and pop the clone as the repaired fixture does. For large values or a latency-sensitive hot path, that cost should be explicit.

If I only need the next few jobs, popping exactly that many is usually cheaper than sorting every item. If I need a complete ordered snapshot, conversion or a separate sorted representation may be clearer.

into_sorted_vec has the opposite orientation

into_sorted_vec consumes the heap and returns an ascending vector. RFA-193 documents this easy-to-miss direction.

Repeated pop from a max heap yields descending values. into_sorted_vec returns ascending values. Both are ordered and both consume, but they are not interchangeable.

I name the required orientation in tests and APIs: highest_first or ascending_snapshot is better than ordered.

The first iterator item is not a useful promise

The current backing representation places a greatest value at its root, so ordinary iteration begins there. Because the method's public order is arbitrary, I do not use iter().next() as a substitute for peek().

peek states the maximum guarantee directly and returns None for an empty heap. Code communicates better when it invokes the operation matching its requirement.

Similarly, I do not use iteration position as an external job identifier. Pushes and pops can rearrange storage while preserving heap semantics.

Equal priorities need a tie policy

Even repeated popping cannot invent a stable business order among elements whose Ord values compare equal. If FIFO among equal priorities matters, I include a monotonic sequence number in the ordering key with the desired direction.

That sequence becomes part of the data structure's contract. Without it, tests should accept any equal-priority representative order.

For min-heap behavior, Reverse changes comparison direction. It does not make iter sorted; the backing storage remains only heap-ordered under the reversed comparison.

Iteration is still valuable

Arbitrary order does not mean random sampling or unstable membership. Iteration visits every current element once. It works for aggregates whose result is order-independent, debugging membership, or copying into another structure.

Floating-point accumulation is not mathematically order-independent at machine precision, so even a “sum all values” use may require a deterministic policy. I do not promise reproducible output based on the current internal layout.

What I test

The repaired program clones the heap, repeatedly pops it, and asserts 4, 3, 2, 1. It also confirms the original heap still holds four items.

I test empty and single-item heaps, mixed priorities, equal priorities, minimum and maximum keys, and the chosen tie rule. Performance tests measure how many ordered items are actually requested, because cloning and draining everything may not fit the use case.

The core principle is that data-structure invariants are narrower than familiar visual interpretations. A binary heap guarantees access to one extreme and enough partial order to repair it efficiently. iter exposes membership in arbitrary storage order; priority order requires the operation that repeatedly restores the root guarantee.