Heap: container or range?

[Bill Baxter]

On Fri, Jan 30, 2009 at 1:17 PM, Andrei Alexandrescu
<SeeWebsiteForEmail at erdani.org> wrote:
> Bill Baxter wrote:
>>
>> On Fri, Jan 30, 2009 at 12:14 PM, Andrei Alexandrescu
>>>
>>> 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?
>
> 'a' is messed up (mutated) by definition. The problem is that after h was
> copied to do take's deed, it got messed up (i.e., doesn't respect the heap
> property anymore).
>
>> 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.
>
> Yah, that should work. You just need to initially fill the heap with the
> numbers 0 to arrayOfHeavies.length. I presume that's what you meant with the
> illegal slicing notation :o).

Ok. great.  I thought that the slicing notation to make a sequence
worked everywhere now in D2.  I guess it's only inside a foreach.

--bb