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
