在hackage上可以找到大量的优先级队列实现，以完成您的列表：

• 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

其中我发现PSQueue有一个非常好的界面。我想这是第一个实现之一，在 this纸由拉尔夫Hinze。它可能不是最高效和最完整的实现，但到目前为止它满足了我的所有需求。

MonadReader中有一篇非常好的文章（ issue 16 ），由Louis Wassermann撰写（他还写了 pqueue 包）。在他的文章中，路易给出了各种不同的优先级队列实现，并且还包括了每种优先级队列的算法复杂性。
作为一些优先级队列内部简单性的突出例子，他包含了一些很酷的小实现。我最喜欢的一篇（摘自他的文章）：

  data SkewHeap a = Empty | SkewNode a（SkewHeap a）（SkewHeap a）派生（显示）

（+++）:: Ord a => SkewHeap a  - > SkewHeap a  - > SkewHeap a 
 heap1 @（SkewNode x1 l1 r1）+++ heap2 @（SkewNode x2 l2 r2）
 | x1  |否则= SkewNode x2（heap1 +++ r2）l2 
空++ ++ heap =堆$ b $ heap +++空=堆

 extractMin空=无
 extractMin（SkewNode xlr）= Just（x，l +++ r）
 

一个简短的用法示例：

  test = foldl（\acc x-> acc +++ x）空节点
 where nodes = map（\x-> SkewNode x Empty Empty）[3,5,1,9,7,2] 
 

优先级队列实现的一些基准可以在这里找到和haskell中一个非常有趣的线程。 org 此处。

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

• Data.PriorityQueue.FingerTree (in fingertree-0.0.1.0 on hackage)
• Data.PurePriorityQueue (in pure-priority-queue-0.14 on hackage)

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

• Data.Heap (in heap-1.0.0 on hackage)

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

• Data.Heap (in heaps-0.2 on hackage)
• Data.MeldableHeap (in meldable-heap-2.0.3 on hackage)

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?

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.