On 16 Jun 2009, at 11:49 am, Bertram Felgenhauer wrote:
What about decreaseKey in a purely functional setting? I suppose it's
O(log n), based on the intuition of trees with limited branching
factor.
Fibonacci heaps can do it in O(1), which makes a difference for
Dijkstra's algorithm, for example.
The original poster in the Erlang thread on the subject
didn't ask for decreaseKey.
The problem with delete and decreaseKey is that they require a
way of identifying en entry _within_ a priority queue. This is
easy enough to do in C or Java: just hand out pointers to the
internal nodes. It's less easy in a language where nodes don't
_have_ identities, such as Haskell or Erlang. The Brodal and
Okasaki paper suggests using an extra dictionary data structure
for this purpose, roughly doubling the size of the whole thing.
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
