Pure heap data structure with efficient decreaseKey
dbueno
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.
-Denis
[0] http://www.eecs.usma.edu/webs/people/okasaki/pubs.html
[1] http://scholar.google.com/scholar?hl=en&lr=&cluster=11761200966844597000
Ben Franksen
> 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
dbueno
> 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
dbueno
> 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
Ben Franksen
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