# Append Vec to BinaryHeap?

**URL:** <https://internals.rust-lang.org/t/append-vec-to-binaryheap/15209>\
**Category:** Uncategorized\
**Created:** [August 22, 2021, 6:30pm UTC](https://internals.rust-lang.org/t/append-vec-to-binaryheap/15209 "2021-08-22T18:30:20Z")\
**Posts on this page:** 14\
**Page:** 1

<div class="post-metadata">

**Author:** ![Neutron3529](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/neutron3529/32/6976_2.png) [@Neutron3529](https://internals.rust-lang.org/u/Neutron3529)\
**Post date:** [August 22, 2021, 6:30pm UTC](https://internals.rust-lang.org/t/append-vec-to-binaryheap/15209/1 "2021-08-22T18:30:20Z")

</div>

AFAIK, there only exists a function that append BinaryHeap to a BinaryHeap, but its implememtation is just append a Vec to BinaryHeap. If someone really want to append a vec to the BinaryHeap, the conversion from Vec to BinaryHeap cost some time and it is a totally waste since the source code is

```rust
    #[stable(feature = "binary_heap_append", since = "1.11.0")]
    pub fn append(&mut self, other: &mut Self) {
        if self.len() < other.len() {
            swap(self, other);
        }

        let start = self.data.len();

        self.data.append(&mut other.data);//regard `&mut other.data` as a `Vec`, rather than a `BinaryHeap`.

        self.rebuild_tail(start);// assume self.data[0..start] is a vaild heap.
    }

```

things might be better changing the function to

```rust
    #[stable(feature = "binary_heap_append", since = "1.11.0")]
    pub fn append(&mut self, other: &mut Self) {
        if self.len() < other.len() {
            swap(self, other);
        }
        self.append_vec(&mut other.data)
    }
    pub fn append_vec(&mut self, vec: &mut Vec<T>){ // not tested, maybe something simillar like what I've shown below.
    // T is defined in `impl <T:Ord> for BinaryHeap`, no need to re-define it.
        let start = self.data.len();
        self.data.append(vec);
        self.rebuild_tail(start);
    }

```

Is it worth a PR or just a Pre-RFC?

If you find it could be an acceptable choice, please help me submit the PR and leave a message here. Due to some reason, I can hardly connect to github. I would be appreciate that you help me submit this possible PR.

Anyway, thank you for reading:)

---

<div class="post-metadata">

**Author:** ![steffahn](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/steffahn/32/13288_2.png) [@steffahn](https://internals.rust-lang.org/u/steffahn)\
**Post date:** [August 22, 2021, 7:07pm UTC](https://internals.rust-lang.org/t/append-vec-to-binaryheap/15209/2 "2021-08-22T19:07:45Z")

</div>

You’ll usually use the [`.extend(…)`](https://doc.rust-lang.org/1.54.0/std/collections/struct.BinaryHeap.html#method.extend) method to append from a different collection. In order to do it with a `&mut Vec<T>` and keep it’s allocation and capacity intact, you can use `Vec::drain`. I.e. your proposed `heap.append_vec(&mut vector)` would behave similar to or the same as `heap.extend(vector.drain(..))`.

* * *

```rust
use std::collections::BinaryHeap;

pub fn append_binary_heap_with_vec<T: Ord>(heap: &mut BinaryHeap<T>, vector: &mut Vec<T>) {
    heap.extend(vector.drain(..));
}

```

(in [the playground](https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=a2c02b5e13c718e606fce14e0b900fe8))

---

<div class="post-metadata">

**Author:** ![SkiFire13](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/skifire13/32/7579_2.png) [@SkiFire13](https://internals.rust-lang.org/u/SkiFire13)\
**Post date:** [August 22, 2021, 8:16pm UTC](https://internals.rust-lang.org/t/append-vec-to-binaryheap/15209/3 "2021-08-22T20:16:56Z")

</div>

However looks like extending a `BinaryHeap` with a `Drain` falls back to just `push`ing each element, which may be much slower than rebuilding the heap if the `Drain` contained a lot of elements.

---

<div class="post-metadata">

**Author:** ![steffahn](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/steffahn/32/13288_2.png) [@steffahn](https://internals.rust-lang.org/u/steffahn)\
**Post date:** [August 22, 2021, 8:59pm UTC](https://internals.rust-lang.org/t/append-vec-to-binaryheap/15209/4 "2021-08-22T20:59:39Z")

</div>

Good catch. Maybe we should simply change

```rust
    fn extend_desugared<I: IntoIterator<Item = T>>(&mut self, iter: I) {
        let iterator = iter.into_iter();
        let (lower, _) = iterator.size_hint();

        self.reserve(lower);

        iterator.for_each(move |elem| self.push(elem));
    }

```

to look more like

```rust
    pub fn append(&mut self, other: &mut Self) {
        if self.len() < other.len() {
            swap(self, other);
        }

        let start = self.data.len();

        self.data.append(&mut other.data);

        self.rebuild_tail(start);
    }

```

i.e. something like:

- reserve lower
- for\_each: push to the underlying vec
- finally, rebuild\_tail

Regarding panic-safety, we don’t need leave the heap in a valid state (w.r.t. the ordering) in case of a panic.

Actually… we could just use `extend` on the `Vec`tor, right?

```rust
    fn extend_desugared<I: IntoIterator<Item = T>>(&mut self, iter: I) {
        let start = self.data.len();

        self.data.extend(iter);

        self.rebuild_tail(start);
    }

```

---

<div class="post-metadata">

**Author:** ![CAD97](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/cad97/32/3460_2.png) [@CAD97](https://internals.rust-lang.org/u/CAD97)\
**Post date:** [August 23, 2021, 12:59am UTC](https://internals.rust-lang.org/t/append-vec-to-binaryheap/15209/5 "2021-08-23T00:59:53Z")

</div>

There's also the possibility of "just" specializing to do the efficient thing here.

---

<div class="post-metadata">

**Author:** ![Neutron3529](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/neutron3529/32/6976_2.png) [@Neutron3529](https://internals.rust-lang.org/u/Neutron3529)\
**Post date:** [August 23, 2021, 4:18am UTC](https://internals.rust-lang.org/t/append-vec-to-binaryheap/15209/6 "2021-08-23T04:18:22Z")

</div>

That could be a really cool choice

..Since I finally figure out that, for `std::Vec`, `.extend` seems as fast as `.copy_from_slice`.

* * *

This question could be mark as `solved` if a PR is submitted to github.

But... I just found another problem: why we couldn't operate `private` fields or methods?

The first solution for me is, try `unsafe{BinaryHeap.data.extend(iter)}`, I know operate private field could be **very** _unsafe_, but I know what I am doing..

Why couldn't we operate private field even with the unsafe block?

access to private field, at least, is safer than `std::mem::transmute`, why we have the latter one?

---

<div class="post-metadata">

**Author:** ![scottmcm](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/scottmcm/32/2355_2.png) [@scottmcm](https://internals.rust-lang.org/u/scottmcm)\
**Post date:** [August 23, 2021, 4:59am UTC](https://internals.rust-lang.org/t/append-vec-to-binaryheap/15209/7 "2021-08-23T04:59:07Z")

</div>

`BinaryHeap::append` already has [heuristics for how to do that](https://github.com/rust-lang/rust/pull/77435/files); updating `extend` to do the same seems perfectly reasonable. (Though generally-descending vs unknown-order can affect things slightly.)

> [@Neutron3529](#):
>
> Why couldn't we operate private field even with the unsafe block?

Because it's important to let libraries change internal implementation details without breaking compilation. It's unacceptable to say that you can't even rename private fields without a major version bump.

---

<div class="post-metadata">

**Author:** ![SkiFire13](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/skifire13/32/7579_2.png) [@SkiFire13](https://internals.rust-lang.org/u/SkiFire13)\
**Post date:** [August 23, 2021, 8:12am UTC](https://internals.rust-lang.org/t/append-vec-to-binaryheap/15209/8 "2021-08-23T08:12:27Z")

</div>

> [@steffahn](#):
>
> ```rust
> fn extend_desugared<I: IntoIterator<Item = T>>(&mut self, iter: I) {
> let start = self.data.len();
> 
> self.data.extend(iter);
> 
> self.rebuild_tail(start);
> }
> 
> ```

> [@CAD97](#):
>
> There's also the possibility of "just" specializing to do the efficient thing here.

At this point specializing would just enable a more limited version of the `swap` trick used in `append` (but just for copying less memory, it wouldn't work to reduce the number of comparisons) and I'm not sure how important that may be.

---

<div class="post-metadata">

**Author:** ![Neutron3529](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/neutron3529/32/6976_2.png) [@Neutron3529](https://internals.rust-lang.org/u/Neutron3529)\
**Post date:** [August 24, 2021, 6:42am UTC](https://internals.rust-lang.org/t/append-vec-to-binaryheap/15209/9 "2021-08-24T06:42:48Z")

</div>

I found a solution

```rust
// RebuildTail is a struct that ensure `rebuild_tail` in `fn extend_desugared`
// is executed
struct RebuildTail<'a, T: Ord>(&'a mut BinaryHeap<T>, usize);
impl<'a, T: Ord> Drop for RebuildTail<'a, T> {
    #[inline]
    fn drop(&mut self) {
        self.0.rebuild_tail(self.1);
    }
}

impl<T: Ord> BinaryHeap<T> {
    fn extend_desugared<I: IntoIterator<Item = T>>(&mut self, iter: I) {
        let start=self.data.len();
        let extend=RebuildTail(&mut self, start);
        extend.0.data.extend(iter);
        // `self.rebuild_tail(start)` is done by `drop(extend)`
    }
}

```

even the iterator panic, the `rebuild_tail` is executed.

Now I am fighting with github... It is not easy for me to connect the github...

The PR is [here](https://github.com/rust-lang/rust/pull/88282)

---

<div class="post-metadata">

**Author:** ![hyeonu](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/hyeonu/32/2162_2.png) [@hyeonu](https://internals.rust-lang.org/u/hyeonu)\
**Post date:** [August 24, 2021, 8:16am UTC](https://internals.rust-lang.org/t/append-vec-to-binaryheap/15209/10 "2021-08-24T08:16:19Z")

</div>

> [@Neutron3529](#):
>
> I found a solution

But we don't have the problem. The `BinaryHeap<T>`'s document says:

> The behavior resulting from such a logic error is not specified, but will not result in undefined behavior. This could include panics, incorrect results, aborts, memory leaks, and non-termination.

Keeping heap ordering after the panic is not needed nor expected.

---

<div class="post-metadata">

**Author:** ![SkiFire13](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/skifire13/32/7579_2.png) [@SkiFire13](https://internals.rust-lang.org/u/SkiFire13)\
**Post date:** [August 24, 2021, 8:28am UTC](https://internals.rust-lang.org/t/append-vec-to-binaryheap/15209/11 "2021-08-24T08:28:45Z")

</div>

> [@hyeonu](#):
>
> > The behavior resulting from such a logic error is not specified, but will not result in undefined behavior. This could include panics, incorrect results, aborts, memory leaks, and non-termination.
> 
> Keeping heap ordering after the panic is not needed nor expected.

Doesn't that "panic" refer to what the `BinaryHeap` could do if you modify an element such that its ordering compared to the other elements changes. Although it's true that currently any `BinaryHeap`'s method doesn't keep the heap ordering if the comparison function panics (and this includes the proposed solution)

---

<div class="post-metadata">

**Author:** ![Neutron3529](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/neutron3529/32/6976_2.png) [@Neutron3529](https://internals.rust-lang.org/u/Neutron3529)\
**Post date:** [August 24, 2021, 8:35am UTC](https://internals.rust-lang.org/t/append-vec-to-binaryheap/15209/12 "2021-08-24T08:35:51Z")

</div>

The question is not just what belongs to the BinaryHeap.

if `self.data.extend(iter)` panics (just the iter panics), the heap should keep its order, but in the previous implementation of @steffahn `self.rebuild_tail(start);` could not be executed.

That is what I want to provide (although I wasn't realized that the compare function could also panic then..)

---

<div class="post-metadata">

**Author:** ![steffahn](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/steffahn/32/13288_2.png) [@steffahn](https://internals.rust-lang.org/u/steffahn)\
**Post date:** [August 24, 2021, 9:21am UTC](https://internals.rust-lang.org/t/append-vec-to-binaryheap/15209/13 "2021-08-24T09:21:23Z")

</div>

In Rust, mutable references are [generally not](https://doc.rust-lang.org/1.54.0/std/panic/trait.UnwindSafe.html#impl-UnwindSafe-10) considered unwind safe which means that using them anyway after catching a panic is always a logic error (unless the type in question specifies that it isn’t).

Also, the `Ord` function panicking with `append`, or the `Ord` function _or closure_ panicking [in `retain` (the other usage of `rebuild_tail` currently)](https://doc.rust-lang.org/1.54.0/src/alloc/collections/binary_heap.rs.html#799) leads to a broken binary heap as-well.

---

<div class="post-metadata">

**Author:** ![system](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/system/32/14092_2.png) [@system](https://internals.rust-lang.org/u/system)\
**Post date:** [November 22, 2021, 9:21am UTC](https://internals.rust-lang.org/t/append-vec-to-binaryheap/15209/14 "2021-11-22T09:21:40Z")

</div>

Closed on November 22, 2021, 9:21am UTC

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.