Bill Baxter wrote:
On Fri, Jan 30, 2009 at 11:49 AM, Andrei Alexandrescu
<[email protected]> 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!!
Andrei
