Heap: container or range?

[Andrei Alexandrescu]

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!!


Andrei