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
I think this depends on whether heap operations are required (and
usable) in places other than in a heap container.
For some applications (certain graph algorithms), you want two ways to
access the data. You use an IndexedPriorityQueue structure, which
contains both a heap of (key, value) pairs ordered by value, allowing
you to pop the item with minimum value in O(log n) time, and also an
array allowing you to access any item by key in O(1) time. Whenever you
move items in the heap, you update the array at the same time.
It's impossible to implement such a data stucture using STL heap
primitives, and likewise, my guess is that it would be impossible in
both a range and container Heaps (basically, you need to be able to hook
in a user-defined function to be called whenever items are swapped in
the heap).
But if it is possible in one but not the other implementation, it should
be favoured.
