std.algorithm.BinaryHeap

[Andrei Alexandrescu]

bearophile wrote:
> Andrei Alexandrescu:
>> These topology choices are used with SListRange (independent,
>> growable singly-linked list vs. a range looking at a different
>> singly-linked list). If the notion of topology turns out to be a
>> good design, today's BinaryHeap is Topology.fixed, whereas a
>> BinaryHeap that is Topology.flexible can grow no problem.
> 
> Do you mean that an heap that allows pop() to remove items is
> Topology.fixed?? Is extending a dynamic array a change in its
> topology?

Not pop because reducing a range does not modify the topology. Growing
is the issue.

> I think you are over-generalizing a bit here. 99% of the times I just
> need a heap to push and pop items from it (eventually even many at
> the same time), and I don't care much of its internal implementation
> (that may be a dynamic array of pointers to large blocks of items,
> like a Deque, but with internal blocks not necessarily fully filled
> of items). Using a linked list to implement a binary heap doesn't
> sound like much efficient). So I suggest to use a simpler API, that
> takes a range, builds some internal representation, and allows me to
> push and pop items... Your design is more efficient (no copying data,
> for example) but its API is more hairy. Most people most of the time
> don't want to mess with such details.

If you look at the use of BinaryHeap inside std.algorithm (topNCopy and 
topNIndex, two rather important basic algorithms) you'll see that a heap 
that organizes an existing range is the way to go.

I agree that efficiency consideration don't have to make the interface 
obtuse. A good solution is to provide configurable libraries that make 
everybody happy.

> From what you say I guess there is currently no way to add items to
> an heap.

There isn't an efficient method (you could rebind the heap to a 
different array). The point is that it doesn't exist not because I 
believe it's not necessary, but because I am looking for a good way to 
provide it.


Andrei