Heap: container or range?

[Bill Baxter]

On Fri, Jan 30, 2009 at 12:14 PM, Andrei Alexandrescu
<SeeWebsiteForEmail at erdani.org> 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!!

Messed 'h' up or messed 'a' up?

Anyway, in that case it would be nice if you can easily run the heap
indirectly on an index or pointer buffer.

Will something like this work?
HeavyElement[] arrayOfHeavies;
auto h = Heap!(int[], (int i, int j){return
arrayOfHeavies[i]<arrayOfHeavies[j];} )( 0..arrayOfHeavies.length )

Now   arrayOfHeavies[h.pop()] should give you the smallest element of
the array of heavies, without ever having to copy/swap anything but
ints.

--bb