[Haskell-cafe] Priority queues (was re: refs)

[Jan-Willem Maessen]

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 at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe