std.algorithm.BinaryHeap

[Jason House]

Given the rstricted use of std.algorithm's binary heap, what would be tge recommended way to implement Dijkstra's algorithm. Basically, the way I'd implement it is as follows:

1. Push nodes from edges connected to root onto heap using weights as key
2. Pop lowest value from heap
3. If connected node is endpoint, stop
4. Push nodes from edges connecting to popped node back on heap
     (weight = value popped + edge weight)

It's very simple, but requires growth...

Andrei Alexandrescu Wrote:

> 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