Comparison of Priority Queue implementations in Haskell

59
votes

There seem to be several priority queue implementations available off-the-shelf for Haskell. For instance, there's:

both of which appear to be pure priority queue data structures. The former is based on finger trees, a data structure with which I'm unfamiliar; the latter is a wrapper around Data.Map. There's also

which defines purely functional heap data structures from which one can trivially make priority queues. . There're also

which both implement purely functional meldable heaps using the Brodal/Okasaki data structure, which I believe is analogous to the binomial heap data structure in non-pure functional land.

(Oh, and there's also

  • Data.PriorityQueue (in priority-queue-0.2.2 on hackage)

whose function is unclear to me, but which seems to be related building priority queues attached to a monad, and which seems to be built on top of Data.Map anyhow. In this question, I'm concerned with purely functional priority queues, so I think the priority-queue-0.2.2 package is irrelevant. But correct me if I'm wrong!)

I need a pure functional priority queue data structure for a project I'm building. I was wondering if anyone could provide any words of wisdom as I decide between the embarrassment of riches provided by hackage. Specifically:

  1. Suppose I want do features apart from the traditional priority queue insert and extract-min operations, in a purely-functional/immutable presentation. What are the pros and cons of the packages mentioned above? Does anyone have experience using any of them 'in anger'? What are the tradeoffs in performance? Reliability? Which are used more widely by others? (Using those might make my code easier for others to read, since they will be more likely to be familiar with the library.) Are there any other things I should know before making a decision between them?
  2. If I also want efficient merging of priority queues, what then? (I don't for this project, but I thought adding this but would make the SO question more useful for future readers.)
  3. Are there any other priority queue packages out there that I missed out?
1
haskell
"finger trees, a data structure with which I'm unfamiliar" I very much recommend reading the paper soi.city.ac.uk/~ross/papers/FingerTree.html: it is very clearly written and the data structure is widely useful. Priority queue are specifically discussed, among other applications. – Alexey Romanov
I'm the author of priority-queue-0.2.2 - it was one of my very early endeavors in Haskell and while i've never actually found or been notified of any problems with that version, it's almost certainly not as well-thought-out as the others. Its purpose is indeed for use mostly with IORef, STRef, et al. It could be used in State/StateT for a "pure" interface, but is really not worth the trouble of doing so when there are so many other options out there (including just plain "Map", which has 'minView' and 'maxView' functions). – mokus

1 Answers

42
votes

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

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.