Heap: container or range?

[Jason House]

Andrei Alexandrescu Wrote:

> Bill Baxter wrote:
> > On Fri, Jan 30, 2009 at 11:49 AM, Andrei Alexandrescu
> > <SeeWebsiteForEmail at erdani.org> wrote:
> >> A "computer science heap" is a structure that offers fast access to the
> >> largest element and fast extraction of it (which in turn provides access to
> >> the next largest element etc.).
> > 
> > In response to your previous question of how to distinguish from a
> > memory heap, you can use the specific name for the kind of heap it is,
> > like BinaryHeap, Binomial Heap, Fibbonocci Heap, etc.
> 
> BinaryHeap it is. Thanks!
> 
> >> I'm just done working on the heap in std.algorithm. Now, it turns out that
> >> heap supports both a meaningful definition as a full-fledged container, and
> >> a beautiful definition as a range.
> >>
> >> If Heap is a range, you initiate it with another range, which Heap organizes
> >> in the heap manner. Then, successive calls to next() nicely extract elements
> >> starting from the largest. If the underlying range supports put(), then Heap
> >> also supports put() to insert into the heap.
> >>
> >> Heap as a container would offer similar primitives but in addition would
> >> "own" its data (would call destructors upon destruction, and would support
> >> value copying).
> >>
> >> What do you think? Should I make Heap a container or a range?
> > 
> > Both sound useful depending on circumstances.  One provides the
> > all-in-one convenient solution, the other is more of a "non-invasive
> > heap".
> > 
> > If you emphasize the non-invasive version, then creating the
> > all-in-one version out of that should be pretty easy.  But you can't
> > take an all-in-one and turn it non-invasive so easily.
> 
> Ah, never mind all that. I realized that I can't have a heap range. This 
> is because heaps must mutate the underlying range in-place and any copy 
> will mess the heap up. Here's the example that clarify it for me:
> 
>          int[] a = [ 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 ];
>          auto h = Heap!(int[])(a);
>          assert(equal(take(5, h) == [ 8, 9, 10, 14, 16 ]);
> 
> At this point the mutations done by take messed up h already!!

I would have expected index take(h,5)[0] to be 16...

I still have yet to come to terms with passing ranges by value. I would expect take to modify my range. I naturally expect heaps to be destructive as elements are taken out. I also expect ranges to shrink. I don't see any issue...