dbueno wrote:
> On Mar 14, 10:06 pm, Ben Franksen <ben.frank...@[EMAIL PROTECTED]
> wrote:
>> 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.
Depending on which programming language you are using, it might be helpful
to know that an implementation of general purpose (annotated)
2-3-fingertrees is already available for Haskell, see
http://hackage.haskell.org/cgi-bin/hackage-scripts/package/fingertree-0.0.
In case you are using a strict language, remember that the (amortized)
efficiency of this data structure crucially depends on lazyness (in
certain
places, the paper explains where, but you might have skipped the relevant
parts on first reading); you would have to code this lazyness explicitly.
Cheers
Ben
|
