# tldr

TODO

• Add .into_iter_sorted() method to BinaryHeap

# original post

``````    use std::collections::*;

let heap = BinaryHeap::from(vec![1, 8, 5, 6, 3, 4, 0, 9, 7, 2]); // max heap from a vec
assert_eq!(
heap.into_iter().collect::<Vec<_>>(),
vec![9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
);
``````

https://play.rust-lang.org/?gist=47204085119fcfc3e70b83a404d91a05&version=stable&mode=debug

produces the following error:

``````   Compiling playground v0.0.1 (file:///playground)
Finished dev [unoptimized + debuginfo] target(s) in 0.97 secs
Running `target/debug/playground`
thread 'main' panicked at 'assertion failed: `(left == right)`
left: `[9, 8, 5, 7, 3, 4, 0, 6, 1, 2]`,
right: `[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]`', src/main.rs:7:5
note: Run with `RUST_BACKTRACE=1` for a backtrace.
``````

For me this is surprising but the lib reference says it is correct.

I use BinaryHeap inorder to get the values in max-first order.
It is ridiculous to return values in arbitrary order.
[/Edit]

Itâs just a thin wrapper of the underlying vectorâs iterator.
How can I get the values of max heap in the max-first order using iterator?

My opinion is that `Iterator` for `BinaryHeap` should abstract the following use case (sorry, C++):

``````    while(!q.empty()) {
std::cout << q.top() << " ";
q.pop();
}
std::cout << '\n';
``````

[/Edit]

Why is this surprising to you?

To convert it into a sorted vector use into_sorted_vec.

1 Like
``````extern crate itertools;

fn main() {
use std::collections::BinaryHeap;

let heap = BinaryHeap::from(vec![1, 8, 5, 6, 3, 4, 0, 9, 7, 2]); // max heap from a vec
assert_eq!(
itertools::unfold(heap, |heap| heap.pop()).collect::<Vec<_>>(),
vec![9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
);
}
``````

Edit: Or, if youâd prefer, you can use `unfold(heap, BinaryHeap::pop)`.

2 Likes

It was to me too, because âheap orderâ is pretty useless.

Whereas the sorted iterator is great, especially with combinators like `take` that can take full advantage of its laziness.

It was surprising to me, because:

• `BinaryHeap` is used when you want to get the value in the specified (max-first) order.
• Underlying vector is kind of implementation details, not an interest to the library user.

As a matter of fact, in the current implementation, `heap.into_iter()` is almost identical to `heap.into_vec().into_iter()`. The only benefit, for me, is to save the number of typed charactersâŚ

1 Like

`into_sorted_vec` is min-first order. I could call reverse() or something but inelegant.
For simple app, I could use that technique and get the work done, though.

Thanks, Itâs elegant.

To get a sorted list, I think it would be better to just do a normal vector sort. It seems to me that filling and draining a binary heap is going to cause a lot more memory movements and comparisons than a plain sort. (Although I donât have a reference for that.)

The purpose of BinaryHeap is to get elements in a sorted manner. The current binary heap iterator implementation is useless if you must use external vector sorting.

1 Like

https://doc.rust-lang.org/std/collections/struct.BinaryHeap.html#method.iter

pub fn iter(&self) -> Iter

Returns an iterator visiting all values in the underlying vector, in arbitrary order.

The lib doc says âarbitrary orderâ.
Fortunately, the concept of âarbitrary orderâ includes âmax-first orderâ.
So I suppose fixing this behavior is backward compatible

4 Likes

Do you know how a binary heap works? Internally it is only partially ordered. The only way to get things out in order is to drain it. So unless the iterator drains the heap (i.e. empties it, which is a destructive operation), an iterator cannot give you the items in order.

This doesnât make the heap useless because what a heap is good at is when remove and add operations are mixed or interleaved. If youâre just doing 20xAdd then 20xRemove, then the heap isnât the best data structure for the job.

2 Likes

Okay, to add to this. Maybe they could make the `drain` method return things in order, because that is destructive, which would make the OP happy. Perhaps thereâs a good reason not to do that âŚ Iâm not sure. However, still pushing many items and then popping many items in a BinaryHeap will be less efficient than just putting them in a vector and sorting them, because each of those pushes causes readjustment of the binary tree. However it could be as efficient as a heapsort if the data is loaded all at once, and only one readjustment pass is made. It appears that `BinaryHeap::from(vec)` does that. So if it is being used primarily for sorting a batch of items then thatâs whatâs needed.

2 Likes

If you definitely need to sort the whole thing, yes.

But the nice thing about iterators is that they can be lazy. If you just want the top 10 things that match a (likely) predicate, say, something like `.into_sorted_iter().filter(...).take(10)` can be substantially faster than sorting the whole set.

4 Likes

Isnât OP talking about `into_iter`? That is a destructive operation just as much as `drain` is, right?

Personal opinion â there are two things that concern me about the proposal here:

1. If `into_iter` is changed, it will give a different order from `iter`, which really canât do an in-order traversal.
2. I donât want my existing `BinaryHeap::into_iter` calls to be slowed down because someone else decided to care about preserving an ordering that means nothing to me. Especially when there are perfectly clear and fast ways to do what is wanted. Does `BinaryHeap` offer another fast way to construct an partial-ordered owned iterator?

I think a healthy compromise would be to add an `into_heap_order_iter` or something instead of rewriting the current one.

1 Like

Sorry, I supposed iter() and into_iter() is the almost the same thing. But in reality the former takes `&self` and the latter takes `self`.

My opinion is the both should take `self` and hence destructive.

Itâs a implementation detail of BinaryHeap. And the use case for BinaryHeap is a (blackbox) priority queue. It should hide the detail, in my opinion.

I donât think itâs a well-thought APIâŚ

Yes it's stable public APIs!

I'd suggest you call `heap.into_vec().into_iter()` instead.

``````    /// Consumes the `BinaryHeap` and returns the underlying vector
/// in arbitrary order.
///
#[stable(feature = "binary_heap_extras_15", since = "1.5.0")]
pub fn into_vec(self) -> Vec<T> {
self.into()
}
``````
1 Like

Youâre right, I missed that. Thanks for the correction.

1 Like

You are right, main usage of BinaryHeap is push() and pop(). I actually only used in that way:

Interesting point! You are right.

Maybe:

-- fn heap_iter(self) // destructive; moved
-- fn heap_into_iter(self) // destructive; moved
-- fn heap_drain(&mut self) // destructive; you can use the original heap later.
• (Optionally) Deprecate old ones.

 But I hesitate to do so because binary_heap.rs is already pretty big. More than 1200 lines!