On Mar 14, 10:06 pm, Ben Franksen <ben.frank...@[EMAIL PROTECTED]
> wrote:
> I don't know about Fibonacci heaps, but I dimly remember (...google,
> google, ...yes!) that 2-3-finger trees support an efficient decreaseKey
> operation. For details
seehttp://www.informatik.uni-bonn.de/III/forschung/publikationen/tr/abst...
Thank you! This is what I was looking for.
> It could be (but I haven't investigated) whether the much simpler
> implementation described
inhttp://www.soi.city.ac.uk/~ross/papers/FingerTree.htmlcan
be used as
well.
Indeed, the paper describing that implementation shows how one can
implement a priority queue, and gives enough detail for implementing
decreaseKey. I was able to implement one pretty quickly, but found it
to be (too) slow (for my expectations). It is not unlikely that I did
something stupid, so I will be investigating.
In any case, many thanks for the pointer.
-Denis
|
