Heap: container or range?

[Don]

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.