[Haskell-cafe] Performance of functional priority queues

Richard O'Keefe ok at cs.otago.ac.nz
Tue Jun 16 21:42:48 EDT 2009

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.

More information about the Haskell-Cafe mailing list