BinaryHeap is a max-heap, and Reverse is the fix

Two classic priority-queue jobs.

pub fn k_smallest(nums: Vec<i64>, k: usize) -> Vec<i64>
pub fn merge_sorted(lists: Vec<Vec<i64>>) -> Vec<i64>

• k_smallest returns the k smallest values, ascending. If k exceeds the input length, return everything. k == 0 returns empty. Duplicates count separately.
• merge_sorted merges several already-ascending lists into one ascending list, keeping duplicates. Empty lists and an empty outer list are fine.

The starter compiles and passes clippy. It fails four of the six test cases, and the failures are not random — they are exactly upside down. That is the problem.

BinaryHeap is a max-heap

let mut h = BinaryHeap::new();
h.push(3); h.push(9); h.push(1);
h.pop()   // Some(9)

If your instincts come from Python’s heapq, Java’s PriorityQueue, or C++’s priority_queue, half of you just got it right and half got it wrong — heapq and Java are min-heaps, C++ is a max-heap. Rust chose max because it follows directly from Ord: the heap keeps the greatest element at the root, for the ordinary meaning of “greatest”. No comparator argument, no key= parameter, no reversed lambda. One rule.

Which leaves the obvious question: how do you get a min-heap?

std::cmp::Reverse

use std::cmp::Reverse;

let mut h = BinaryHeap::new();
h.push(Reverse(3)); h.push(Reverse(9)); h.push(Reverse(1));
h.pop()   // Some(Reverse(1))

Reverse<T> is a one-field tuple struct whose entire contribution to the world is this:

impl<T: Ord> Ord for Reverse<T> {
    fn cmp(&self, other: &Self) -> Ordering { other.0.cmp(&self.0) }
}

It flips the comparison. That is all it is — no runtime cost, no extra field, the same bytes in memory. It is worth staring at for a second, because it is a very small demonstration of a very large idea: a newtype changes behaviour without changing data. The heap did not learn a new mode. You handed it a different type whose Ord says something different, and every generic algorithm that uses Ord — sort_by_key, max, BTreeMap, BinaryHeap — inherits the flip for free.

Destructure it back out in the pattern: while let Some(Reverse(x)) = h.pop().

::: question k_smallest could just sort the input and take k. When is the heap actually better? Sorting is O(n log n) time and, for the k-smallest job, O(n) extra space if you cannot sort in place. The bounded-heap method is O(n log k) time and O(k) space — you keep a max-heap of the best k seen so far, push each new value, and pop the largest whenever the heap grows past k.

For k = 10 out of a billion streaming values, that is the difference between “ten items of memory” and “cannot be done”. For k = n it is strictly worse than sorting. The crossover in practice is not where the asymptotics suggest, because sort is extremely well optimised — so use the heap when k is small relative to n, or when the data arrives as a stream you cannot hold.

Note the deliberate inversion in the algorithm: to find the smallest k you keep a max-heap, because the thing you need cheap access to is the worst item currently in your set — the one to evict. That inversion catches people out every time. :::

The silent wrong answer: into_vec versus into_sorted_vec

A BinaryHeap is stored as a Vec in heap order — every parent is at least as large as its children — which is not sorted order. So:

let h: BinaryHeap<i64> = vec![5, 1, 8, 3, 9, 2, 7].into_iter().collect();

h.clone().into_vec()          // [9, 5, 8, 3, 1, 2, 7]   heap order
h.into_sorted_vec()           // [1, 2, 3, 5, 7, 8, 9]   ascending

Both are Vec<i64>. Both type-check. One of them is the answer and one is an implementation detail leaking out, and if your test data happens to be small or already ordered they can agree by accident. into_vec is O(1) and gives you the backing storage; into_sorted_vec is O(n log n) — it is heapsort’s second phase — and gives you ascending order.

The same warning applies to heap.iter(): arbitrary order, no promises. Never serialise, print, or compare a heap by iterating it. peek() is the only positional guarantee, and it points at the maximum.

Merging with a heap

The k-way merge is the classic use of a priority queue. Push the head of every list, and repeatedly pop the smallest and push the next element from whichever list it came from:

heap.push(Reverse((value, list_index, position)));

Tuples compare lexicographically — first field, then second, then third — so a (value, i, pos) tuple orders by value first, which is what a merge wants. Wrapping the whole tuple in Reverse makes it a min-heap. The extra fields are how you find the next element; they only participate in comparison when two values tie, which for a merge is harmless.

One Ord hazard worth knowing now

If you ever put a custom type in a heap, do not hand-write Ord and derive PartialOrd, or vice versa. clippy denies that combination (derive_ord_xor_partial_ord) because the two must agree — partial_cmp(a, b) must equal Some(cmp(a, b)) — and nothing else checks it. When they disagree, BinaryHeap does not crash; it silently returns the wrong element, forever, in production.

Remember the grade is compile + tests + clippy -D warnings.