[Haskell-cafe] Performance of functional priority queues

[Richard O'Keefe]

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.