Tracking Issue for `alloc::collections::BinaryHeap::as_slice`

[frol]

Feature gate: #![feature(binary_heap_as_slice)]

This is a tracking issue for std::collections::BinaryHeap::as_slice, a method that returns a slice of the data that is stored in the BinaryHeap (the order is arbitrary).

Public API

impl BinaryHeap<T> {
    pub fn as_slice(&self) -> &[T]
}

Steps / History

• [x] Implementation: #82331
• [x] Final commenting period (FCP)
• [x] Stabilization PR

Unresolved Questions

• None yet.

[saolof]

If this is added, it means that the order of the underlying slice is added to the API, which is useful for some purposes. In that case, is it possible to add a .sort_slice() method that just calls .sort() on the underlying Vec, for when you want that slice to be sorted?

This does mean that the implementation details as a binary heap leaks a bit, but there are cases where you do want to alternate between having a sorted array and just having a binary heap.

[dspyz-matician]

This seems useful for efficiently selecting a uniform random element.

[SmnTin]

Can we stabilize it?

[dtolnay]

@SmnTin would you be able to share a link or an explanation of a real-world use case?

@dspyz-matician is this a real use case? In what scenario would you be keeping elements in a BinaryHeap when needing to randomly select among them?

[dspyz-matician]

@dtolnay I have a RRT-like stochastic anytime search algorithm that continually keeps the top N strategies it's found. It randomly selects one of these strategies, clones it, performs a random modification to get a new strategy, then if the new strategy is better than the current worst, it inserts it and pops the current worst one off the top.

[dtolnay]

Thanks!

@rust-lang/libs-api: @rfcbot fcp merge

BinaryHeap::as_slice returns &[T] containing the heap elements in arbitrary order. Regarding whether we should be concerned that exposing the elements in some unspecified order will be problematic, there is already a stable into_vec that returns the heap elements as Vec<T>, also documented as returning them in arbitrary order. (There is also into_sorted_vec, which does a heapsort.)

[rfcbot]

Team member @dtolnay has proposed to merge this. The next step is review by the rest of the tagged team members:

• [x] @Amanieu
• [x] @BurntSushi
• [x] @dtolnay
• [ ] @joshtriplett
• [x] @m-ou-se

No concerns currently listed.

Once a majority of reviewers approve (and at most 2 approvals are outstanding), this will enter its final comment period. If you spot a major issue that hasn't been raised at any point in this process, please speak up!

See this document for info about what commands tagged team members can give me.

[rfcbot]

:bell: This is now entering its final comment period, as per the review above. :bell:

[rfcbot]

The final comment period, with a disposition to merge, as per the review above, is now complete.

As the automated representative of the governance process, I would like to thank the author for their work and everyone else who contributed.

This will be merged soon.