Please explain me whats wrong with binery heap?!!!

Simple example:

import std.container.binaryheap;
import std.stdio;

void main()
{
    int[] a = [ 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 ];
    int[] b = new int[a.length];
    auto h = BinaryHeap!(int[], "a > b")(b, 0);
    foreach (e; a)
    {
        h.insert(e);
    }
    writeln(b); // [1, 2, 3, 4, 7, 9, 10, 14, 8, 16]
    writeln(h); // [1, 2, 3, 4, 7, 8, 9, 10, 14, 16]
    writeln(h.length); // 0 ???????
    h.insert(21);
    writeln(h); // [21] ????????
    writeln(h.length); // 0 ???????
}

On Thursday, 2 April 2020 at 12:59:06 UTC, AlexM wrote:
> Please explain me whats wrong with binery heap?!!!

This has nothing to do with binaryheap and all to do with writeln.
writeln recognizes b and h as ranges, and prints them by iterating over each element, which advances the range to the end. You can see that the following actually prints what you expect:

```
     writeln(b[]);   // [1, 2, 3, 4, 7, 9, 10, 14, 8, 16]
     writeln(h.dup); // [1, 2, 3, 4, 7, 8, 9, 10, 14, 16]
     writeln(h.length); // 10
     h.insert(21);
     writeln(h.dup); // [1, 2, 3, 4, 7, 8, 9, 10, 14, 16, 21]
     writeln(h.length); // 11
```

On Thursday, 2 April 2020 at 12:59:06 UTC, AlexM wrote:
> Please explain me whats wrong with binery heap?!!!
>
> Simple example:
>
> import std.container.binaryheap;
> import std.stdio;
>
> void main()
> {
>     int[] a = [ 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 ];
>     int[] b = new int[a.length];
>     auto h = BinaryHeap!(int[], "a > b")(b, 0);
>     foreach (e; a)
>     {
>         h.insert(e);
>     }
>     writeln(b); // [1, 2, 3, 4, 7, 9, 10, 14, 8, 16]
>     writeln(h); // [1, 2, 3, 4, 7, 8, 9, 10, 14, 16]
>     writeln(h.length); // 0 ???????
>     h.insert(21);
>     writeln(h); // [21] ????????
>     writeln(h.length); // 0 ???????
> }

by iterating over it (writeln doing it) you are taking out all elements from the binary heap. You will either need to .dup it (will cause memory allocation, will only make a single additional copy) or convert it to an array using .array (will cause memory allocation, you can use it multiple times but not use it as binary heap anymore)

If BinaryHeap implemented a save() method it would be possible to do this without duplicating because writeln would call save to not modify the existing data.

If you only want to get the length and do something with the data exactly once, you can call .length before using the data to get the length of the data. If you get length after iterating over your data, your data will be gone at this point.

Otherwise you might want to try some containers library from dub for more advanced containers.

On 4/2/20 8:59 AM, AlexM wrote:
> Please explain me whats wrong with binery heap?!!!
> 
> Simple example:
> 
> import std.container.binaryheap;
> import std.stdio;
> 
> void main()
> {
>      int[] a = [ 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 ];
>      int[] b = new int[a.length];
>      auto h = BinaryHeap!(int[], "a > b")(b, 0);
>      foreach (e; a)
>      {
>          h.insert(e);
>      }
>      writeln(b); // [1, 2, 3, 4, 7, 9, 10, 14, 8, 16]
>      writeln(h); // [1, 2, 3, 4, 7, 8, 9, 10, 14, 16]
>      writeln(h.length); // 0 ???????
>      h.insert(21);
>      writeln(h); // [21] ????????
>      writeln(h.length); // 0 ???????
> }
> 

writeln(h) actually removes all the elements from the heap to print it.

It's also ref-counted, and is not a forward range (no save is provided), so you have to dup it to print it:

writeln(h.dup);

So why would you need to do this? Because heaps have to mutate to iterate. Just printing it needs to move elements around, destroying the original heap in the process.

Another case of why non-forward ranges shouldn't support copying.

-Steve

On 4/2/20 9:25 AM, WebFreak001 wrote:
> If BinaryHeap implemented a save() method it would be possible to do this without duplicating because writeln would call save to not modify the existing data.

A binary heap has to move elements in order to iterate. So a save call would be equivalent to a dup call.

I think that's why it supports dup and not save.

-Steve

On Thursday, 2 April 2020 at 13:23:29 UTC, Dennis wrote:
> writeln recognizes b and h as ranges, and prints them by iterating over each element,

Correction: this only applies to `h`, the array slice `b` will not be mutated by writeln.

On Thursday, 2 April 2020 at 12:59:06 UTC, AlexM wrote:
> Please explain me whats wrong with binery heap?!!!
>
> Simple example:
>
> import std.container.binaryheap;
> import std.stdio;
>
> void main()
> {
>     int[] a = [ 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 ];
>     int[] b = new int[a.length];
>     auto h = BinaryHeap!(int[], "a > b")(b, 0);
>     foreach (e; a)
>     {
>         h.insert(e);
>     }
>     writeln(b); // [1, 2, 3, 4, 7, 9, 10, 14, 8, 16]
>     writeln(h); // [1, 2, 3, 4, 7, 8, 9, 10, 14, 16]
>     writeln(h.length); // 0 ???????
>     h.insert(21);
>     writeln(h); // [21] ????????
>     writeln(h.length); // 0 ???????
> }

Thank you very much for all responders!