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.