On Jun 8, 2005, at 7:13 AM, Gracjan Polak wrote:
Tomasz Zielonka wrote:
[Data.Map can be used to implement priority queues]
Wow, I did not think about this.
As far as I remember in imperative world priority queues had special
implementation, with very good O() characteristics. Is O(log N) the
best thing that can bo done in pure functional setting?
Either insertion or deletion must be amortized O(lg N) unless you're
using bounded priorities. Otherwise you'd be able to sort in better
than O(N lg N) time by using a new improved queue--and that, of course,
is impossible. It doesn't matter what setting you're in.
For bounded priorities, it would be nice to see similar functionality
in Data.IntMap. There, you have to squint funny, but stuff takes
constant time if you assume the number of bits in a word (I believe
this is W in the HaskellDoc) doesn't change. In practice you'd only
pay for as many bits as you use (so if you use keys between -512 and
511, W=10 rather than, say, 32).
To put it another way: is Data.Map only workaround to get something
done, or is it The Right Way of doing PQs in Haskell?
I believe there are heap data structures that make one or the other
operation (insert or deleteMin) O(1). You might try one of Okasaki's
heap implementations from "Purely Functional Data Structures". Heaps
don't need to support lookup, and can focus on doing insertion and
deletion well.
-Jan-Willem Maessen
Best regards
Tomasz
--
Gracjan
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
