Comparison of Priority Queue implementations in Haskell

Solution 1:

There is an abundance of priority queue implementations to be found on hackage, just to complete your list:

• http://hackage.haskell.org/package/PSQueue
• http://hackage.haskell.org/package/pqueue
• http://hackage.haskell.org/package/queuelike
• http://hackage.haskell.org/package/priority-queue
• http://hackage.haskell.org/package/pure-priority-queue
• http://hackage.haskell.org/package/fingertree-psqueue

Out of those I found that PSQueue has an especially nice interface. I guess it was one of the first implementations and is nicely covered in this paper by Ralf Hinze. It might not be the most efficient and complete implementation but so far it has served all my needs.

There is a very good article in the MonadReader (issue 16) by Louis Wassermann (who also wrote the pqueue package). In his article Louis gives a variety of different priority queue implementations and also includes algorithmic complexities for each.
As a striking example of the simplicity of some priority queue internals he includes some cool little implementations. My favorite one (taken from his article):

data SkewHeap a = Empty | SkewNode a (SkewHeap a) (SkewHeap a) deriving (Show)

(+++) :: Ord a => SkewHeap a -> SkewHeap a -> SkewHeap a
heap1@(SkewNode x1 l1 r1) +++ heap2@(SkewNode x2 l2 r2) 
  | x1 <= x2    = SkewNode x1 (heap2 +++ r1) l1 
  | otherwise = SkewNode x2 (heap1 +++ r2) l2
Empty +++ heap = heap
heap +++ Empty = heap

extractMin Empty = Nothing
extractMin (SkewNode x l r ) = Just (x , l +++ r )

Cool little implementation...a short usage example:

test = foldl (\acc x->acc +++ x) Empty nodes
  where nodes = map (\x-> SkewNode x Empty Empty) [3,5,1,9,7,2]

Some benchmarks of priority queue implementations can be found here and in a rather interesting thread on haskell.org here.