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