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.
-Denis
[0] http://www.eecs.usma.edu/webs/people/okasaki/pubs.html
[1]
http://scholar.google.com/scholar?hl=en&lr=&cluster=11761200966844597000
|
