Pure heap data structure with efficient decreaseKey

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 sing 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?h...200966844597000

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 sing 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/I...bstract-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

On Mar 14, 10:06 pm, Ben Franksen <ben.frank...@online.de> 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/publikat
ionen/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.htmlc
an 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

On Mar 14, 10:06 pm, Ben Franksen <ben.frank...@online.de> 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/publikat
ionen/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.htmlc
an 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 wrote:
> On Mar 14, 10:06 pm, Ben Franksen <ben.frank...@online.de> wrote: 
>
> 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/...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