`BinaryHeap::from_raw_vec`

[Dan54]

Proposal

Problem statement

Currently, a BinaryHeap can be constructed in two main ways: either by adding one item at a time to an empty heap, (time $O(n\log n)$) or using BinaryHeap::from::<Vec<_>>(), which does a time $O(n)$ rebuild. However, if a Vec<T> is already structured as a max-heap, then this rebuild is unnecessary, so we could construct the BinaryHeap in constant time.

Motivating examples or use cases

Building a BinaryHeap from data that is already structured as a heap:

let heaped_vec = vec![5,4,3,2,1];
let heap = BinaryHeap::from_raw_vec(heaped_vec);
// or:
let mut data = get_some_data();
fast_heapify(&mut data); // e.g. multithreaded heap build
let heap = BinaryHeap::from_raw_vec(data);

It could also reverse a .into_vec():

let inner_vec = heap.into_vec();
// do something with inner_vec
let heap = BinaryHeap::from_raw_vec(inner_vec);

Solution sketch

impl BinaryHeap<T, A> {
    // Convert a `Vec<T>` to a `BinaryHeap` without rebuilding
    // Safety: `vec` must be a max-heap
    // It is a logic error for `vec` to not be a max-heap, but will not cause UB
    unsafe fn from_raw_vec(vec: Vec<T, A>) -> Self
}

The function could be made safe because BinaryHeap does not rely on the underlying Vec being correctly ordered for its safety (it cannot because Ord is safe), but this could break code that relies on the correctness of BinaryHeap for trusted types like u32.

Alternatives

The alternatives are to either accept the $O(n)$ time of From<Vec<T>> or to create your own implementation of BinaryHeap.

Links and related work

What happens now?

This issue contains an API change proposal (or ACP) and is part of the libs-api team feature lifecycle. Once this issue is filed, the libs-api team will review open proposals as capability becomes available. Current response times do not have a clear estimate, but may be up to several months.

Possible responses

The libs team may respond in various different ways. First, the team will consider the problem (this doesn't require any concrete solution or alternatives to have been proposed):

• We think this problem seems worth solving, and the standard library might be the right place to solve it.
• We think that this probably doesn't belong in the standard library.

Second, if there's a concrete solution:

• We think this specific solution looks roughly right, approved, you or someone else should implement this. (Further review will still happen on the subsequent implementation PR.)
• We're not sure this is the right solution, and the alternatives or other materials don't give us enough information to be sure about that. Here are some questions we have that aren't answered, or rough ideas about alternatives we'd want to see discussed.

[scottmcm]

We should not do this as written because I want to be able to trust that BinaryHeap<u32> actually works because I trust u32 -- same as how there's no way to get an invariants-violating HashSet<u32> or BTreeSet<u32> and such APIs have been previously rejected.

(Said without considering whether an unsafe version should be added. The concern about doing as a safe function doesn't apply if it's changed to unsafe fn instead.)

[Dan54]

We should not do this as written because I want to be able to trust that BinaryHeap<u32> actually works because I trust u32 -- same as how there's no way to get an invariants-violating HashSet<u32> or BTreeSet<u32> and such APIs have been previously rejected.

(Said without considering whether an unsafe version should be added. The concern about doing as a safe function doesn't apply if it's changed to unsafe fn instead.)

I was mainly thinking about BinaryHeap's API when declaring it safe. I have no objection to making it unsafe if this is a concern.