Surprising behavior of BinaryHeap::into_iter()

help
21

This might be a shortest path [Added] than adding three version of functions [/Added].

22

According to RFC 0199, iter() shoud take &self.

https://github.com/rust-lang/rfcs/blob/master/text/0199-ownership-variants.md

In general, Rust's iterator is designed to handle immutable and borrow case well. For inherently mutable collections like a BinaryHeap, we might need special methods rather than standard ones.

23

Yes, I think into_sorted_iter() or into_ordered_iter() (or similar) seems the best solution, and the justification is what @scottmcm said, that sometimes we only want the first few items of a sorted list (e.g. a "top ten" list), without the cost of sorting everything. This could be done efficiently with something like BinaryHeap::from(vec).into_sorted_iter().take(10). This does one "heap condition correction" pass over the data, then just the minimum work to get the first few items.

2 Likes
24

Yes, into_iter() will be faster in general.

BinaryHeap::from(vec).into_iter().take(10);        // O(n); faster
BinaryHeap::from(vec).into_sorted_iter().take(10); // O(n log n)

btw, for naming, I prefer .into_iter_sorted() so that IDE suggests both .into_iter() and .into_iter_sorted() simultaneously. I hope it will increase the chance to notice into_iter() is NOT sorted.

25

I wonder: What is the procedure to take this further? Unless some std maintainer wanders by here, or someone has time to try and do a PR, nothing is going to happen.

26

It seems to be a low-hanging fruit....

The last week, I cloned the rust repo and ran liballoc test which contains BinaryHeap.

I’ll try to add new method and create a PR.

2 Likes