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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
