dbueno wrote:
> In the imperative world, the Fibonacci heap is an occasionally-useful
> data structure that maintains some heap-ordered trees and lets you
> efficiently decrease the keys of elements in the heap. The typical
> representation of a Fibonacci heap is inherently imperative -- it uses
> mutable, circular, doubly-linked lists, and each node keeps mutable
> pointers to parent and child list. In this context, the decreaseKey
> operation consumes a pointer into the tree structure and modifies the
> heap accordingly.
>
> As is well known, using this approach won't work in a pure language.
> Hence I am seeking advice on implementing a pure analogue of the
> Fibonacci heap.
>
> I've looked at Chris Okasaki's publications [0] to see if he discusses
> any heaps supporting the decreaseKey operation, but couldn't find any
> (please correct me if I missed something). I found a paper by David
> King [1] about functional binomial queues which gives a way to
> implement decreaseKey in terms of a binomial queue. This has the
> semantics I'd like, but since Fibonacci heaps were originally
> conceived to asymptotically outdo binomial heaps, I wonder if there
> isn't an analogue of Fibonacci heaps in a functional language.
>
> Any pointers or discussion is appreciated.
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 see
http://www.informatik.uni-bonn.de/III/forschung/publikationen/tr/abstracts/IAI-TR-98-12.abstract-en.html
It could be (but I haven't investigated) whether the much simpler
implementation described in
http://www.soi.city.ac.uk/~ross/papers/FingerTree.html
can be used as
well.
Cheers
Ben
|
