Sebastian Sylvan wrote: > On Mon, Jun 15, 2009 at 4:18 AM, Richard O'Keefe <o...@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 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe