Haskell中优先级队列实现的比较

Haskell似乎有几个可用的优先级队列实现。 例如，有：

• Data.PriorityQueue.FingerTree（在fingertree-0.0.1.0上hackage）
• Data.PurePriorityQueue（在纯粹的优先级队列0.14在hackage）

这两者似乎都是纯粹的优先队列数据结构。 前者是基于手指树，这是我不熟悉的数据结构; 后者是Data.Map的一个包装。 还有

• Data.Heap（在堆 – 1.0.0 hackage）

它定义了纯粹function性的堆数据结构，从这些数据结构中可以轻而易举地创build优先级队列。 。 还有

• Data.Heap（在hackage中为0.2 ）
• Data.MeldableHeap（在haldage的meldable-heap-2.0.3中）

它们都使用Brodal / Okasaki数据结构来实现纯function性的可堆栈堆，我相信它类似于非纯function域中的二项堆数据结构。

（哦，还有

• Data.PriorityQueue（在优先队列-0.2.2上的hackage）

其function对我来说是不清楚的，但似乎与build立monad的优先级队列有关，而且似乎无论如何都是build立在Data.Map之上的。 在这个问题中，我关心的是纯粹的function优先级队列，所以我认为priority-queue-0.2.2包是无关紧要的。 但如果我错了，请纠正我的错误！）

我需要一个纯粹的function优先级队列数据结构为我正在build设的项目。 我想知道是否有人可以提供任何智慧的话，因为我决定在黑客提供的财富尴尬之间。 特别：

1. 假设我想要除了传统的优先级队列插入和extract-min操作之外的function，在纯function/不可变的演示文稿中。 上面提到的软件包有什么优点和缺点？ 有没有人有经验使用他们的任何“愤怒”？ 性能的折衷是什么？ 可靠性？ 哪些被其他人广泛使用？ （使用这些可能会使我的代码更容易被他人阅读，因为他们更可能熟悉图书馆。）在作出决定之前，我还需要了解其他什么吗？
2. 如果我也想要高效的合并优先级队列，那么呢？ （我不是为了这个项目，但是我认为增加这个，但是会让这个问题对于未来的读者更有用。）
3. 有没有其他优先级队列包，我错过了？

Answer 1

在hackage上可以find大量的优先级队列实现，只是为了完成你的列表：

• 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有一个特别好的界面。 我想这是第一个实现，Ralf Hinze在本文中很好地介绍了它 。 它可能不是最有效和最完整的实现，但到目前为止，它满足了我所有的需求。

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

 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 xlr ) = Just (x , l +++ r ) 

很酷的小实施…一个简短的用法示例：

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

有些优先级队列实现的基准可以在这里find，在这里可以find一个相当有趣的haskell.org 线程 。