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
