[Haskell-cafe] Priority queues (was re: refs)
jmaessen at alum.mit.edu
Wed Jun 8 10:49:23 EDT 2005
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
>> Best regards
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
More information about the Haskell-Cafe