Andrei Alexandrescu 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.).
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?
Andrei
regarding your previous question:
isn't a Heap also called a Priority Queue?
