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