Whats wrong with binery heap or i am not understand something?

Steven Schveighoffer schveiguy at gmail.com
Thu Apr 2 13:26:10 UTC 2020


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


More information about the Digitalmars-d-learn mailing list