Heap: container or range?

[Andrei Alexandrescu]

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


Andrei