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