141. BinaryHeap::into_sorted_vec — Heapsort in One Call

You stuffed everything into a BinaryHeap to keep “biggest first” cheap, but at the end of the day you want a sorted Vec to hand to the next stage. The pop-loop you almost wrote is built into the type — into_sorted_vec consumes the heap and gives you the ascending-order Vec for free.

The pop-loop

The naive shape: drain the heap with pop and push into a fresh Vec. Pops come out largest-first, so to get ascending order you have to either reverse at the end or push to the front — both add steps for no reason.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

use std::collections::BinaryHeap;

let heap = BinaryHeap::from([3, 1, 4, 1, 5, 9, 2, 6, 5]);

let mut out = Vec::with_capacity(heap.len());
let mut heap = heap;
while let Some(x) = heap.pop() {
    out.push(x);
}
out.reverse(); // pops came out descending — flip them

assert_eq!(out, [1, 1, 2, 3, 4, 5, 5, 6, 9]);

Five lines and a temporary out for what is, in the end, “sort this thing.” The heap is already a heap — you’ve paid for the structure, now you’re throwing it away.

The one-liner

BinaryHeap::into_sorted_vec(self) -> Vec<T> does exactly the drain-and-sort the heap was built for, in O(n log n), and reuses the heap’s allocation as the output Vec. No reverse(), no spare buffer.

1
2
3
4
5
6

use std::collections::BinaryHeap;

let heap = BinaryHeap::from([3, 1, 4, 1, 5, 9, 2, 6, 5]);
let sorted = heap.into_sorted_vec();

assert_eq!(sorted, [1, 1, 2, 3, 4, 5, 5, 6, 9]);

Ascending order, because that’s almost always what the next consumer wants. BinaryHeap is a max-heap, so internally into_sorted_vec repeatedly sifts the max to the end of the backing buffer — the same in-place heapsort you’d write by hand.

Top-k without sorting the whole input

Where this really pays off: “I want the largest k of n items.” Push everything into the heap with Reverse to make it a min-heap-of-size-k, then call into_sorted_vec once at the end:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

use std::cmp::Reverse;
use std::collections::BinaryHeap;

fn top_k(items: impl IntoIterator<Item = i32>, k: usize) -> Vec<i32> {
    let mut heap: BinaryHeap<Reverse<i32>> = BinaryHeap::with_capacity(k);
    for x in items {
        if heap.len() < k {
            heap.push(Reverse(x));
        } else if let Some(mut min) = heap.peek_mut() {
            if x > min.0 { *min = Reverse(x); }
        }
    }
    heap.into_sorted_vec()
        .into_iter()
        .map(|Reverse(x)| x)
        .collect()
}

assert_eq!(top_k([7, 3, 9, 1, 8, 2, 6], 3), [9, 8, 7]);

into_sorted_vec returns the Reverse-wrapped items in ascending Reverse order, which is descending by inner value — strip the wrapper with map and the largest of the top-k comes out first, exactly the order a “top” list wants.

When to reach for it

Any time the loop you’re about to write is “pop until empty, collect into Vec.” into_sorted_vec is the same algorithm — heapsort — with one fewer allocation and one fewer reverse. The heap was already half of a sort; let it finish the job.