[Haskell-cafe] class Ref...

[Gracjan Polak]

Tomasz Zielonka wrote:
> On Tue, Jun 07, 2005 at 12:25:50PM +0200, Gracjan Polak wrote:
> 
>>Another question: priority queue. In libraries bundled with ghc we have 
>>Data.Queue, but I couldn't find PriorityQueue. Is there somewhere an 
>>implementation that everybody uses, but is not in the library?
> 
> 
> You can use the new Data.Map module for this (old Data.FiniteMap too,
> but a bit more clumsily), it has findMin, findMax, deleteFindMin,
> deleteFindMax, deleteMin, deleteMax. All these operations should have
> O(log N) cost.

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?

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?

> 
> Best regards
> Tomasz

-- 
Gracjan