[Haskell-cafe] class Ref...
gracjan at acchsh.com
Wed Jun 8 07:13:47 EDT 2005
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
More information about the Haskell-Cafe