[Haskell-cafe] Performance of functional priority queues

[Bertram Felgenhauer]

Sebastian Sylvan wrote:
> On Mon, Jun 15, 2009 at 4:18 AM, Richard O'Keefe <ok at cs.otago.ac.nz> wrote:
> > There's a current thread in the Erlang mailing list about
> > priority queues.  I'm aware of, for example, the Brodal/Okasaki
> > paper and the David King paper. I'm also aware of James Cook's
> > priority queue package in Hackage, have my own copy of Okasaki's
> > book, and have just spent an hour searching the web.
> >
> > One of the correspondents in that thread claims that it is
> > provably impossible to have an efficient priority queue implementation
> 
> A priority queue based on skewed binomial heaps is asymptotically optimal
> (O(1) for everything except deleteMin which is O(log n)), so if that's what
> he means by "efficient" then he's most definitely wrong.

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.

regards,

Bertram