Haskell中优先队列实现的比较
Haskell似乎有几个可用的优先级队列实现。 例如，有：
这两者看起来都是纯粹的优先队列数据结构。 前者基于手指树，这是我不熟悉的数据结构; 后者是Data.Map的一个包装。 还有
它定义了纯粹功能性的堆数据结构，从中可以轻松地制定优先级队列。 。 还有
它们都使用Brodal / Okasaki数据结构来实现纯粹功能性的可堆集堆，我相信它类似于非纯功能域中的二项堆数据结构。
（哦，还有
它的功能对我来说还不清楚，但似乎与建立monad的优先级队列有关，而且似乎无论如何都是建立在Data.Map之上的。 在这个问题中，我关心的是纯粹的功能优先级队列，所以我认为priority-queue-0.2.2包是无关紧要的。 但如果我错了，请纠正我的错误！）
我需要一个纯功能优先级队列数据结构，用于我正在构建的项目。 我想知道是否有人能够提供任何智慧的话，因为我决定在黑客提供的财富尴尬之间。 特别：
在hackage上可以找到大量的优先级队列实现，只是为了完成您的列表：
在那些我发现PSQueue有一个特别好的界面。 我想这是第一个实现，并且由Ralf Hinze在本文中很好地覆盖。 它可能不是最高效和最完整的实施方式，但迄今为止它满足了我的所有需求。
MonadReader（问题16）中有一篇非常好的文章，由Louis Wassermann撰写（他也编写了pqueue包）。 在他的文章中，路易给出了各种不同的优先级队列实现，并且还包括了每种算法的复杂性。
作为一些优先队列内部简单的突出例子，他包含了一些很酷的小实现。 我最喜欢的一篇（摘自他的文章）：
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 )
很酷的小实现...一个简短的用法示例：
test = foldl (acc x->acc +++ x) Empty nodes
where nodes = map (x-> SkewNode x Empty Empty) [3,5,1,9,7,2]
有些优先级队列实现的基准测试可以在这里找到，在这里可以找到一个相当有趣的haskell.org线程。
链接地址: http://www.djcxy.com/p/43239.html上一篇: Comparison of Priority Queue implementations in Haskell