Search code examples
sortingrustheapsort

In-place heapsort using std::collections::BinaryHeap

I'd like to create an in-place heapsort function in Rust. In the standard library I found std::collections::BinaryHeap that looked promising. I am able to use it to create a function consuming its argument:

use std::collections::BinaryHeap;

fn heapsort<T: Ord>(list: Vec<T>) -> Vec<T> {
    let heap = BinaryHeap::from(list);
    heap.into_sorted_vec()
}

The docs state that "converting a vector to a binary heap can be done in-place", but I am having trouble creating one that works on a reference and can do it in-place (heapsort<T: Ord>(list: &mut Vec<T>)). Can I achieve it using only std::collections::BinaryHeap?

Solution

  • I am having trouble creating one that works on a reference and can do it in-place

    BinaryHeap is built on top of Vec. When you create a new heap from a Vec, you have to give it complete ownership. It will then ensure that the vector is in a good state to act as a heap.

    Since a BinaryHeap is not built on top of a &mut Vec (which would mostly have horrible ergonomics), you cannot do that.

    It's unclear why you don't just use slice::sort on the vector.

    the docs state that "converting a vector to a binary heap can be done in-place"

    To clarify, the documentation is correct - there's no extra memory allocation needed, thus it is in-place. The important aspect is that the BinaryHeap owns its data and doesn't expose all the internals out to the world.

    What you are asking for is the ability to call rebuild on a user-supplied vector. To me, this has dubious usefulness, but you could always submit an RFC to expose it.