Heap: container or range?

[Bill Baxter]

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.


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

--bb