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

Question

Haskell似乎有几种现成的优先级队列实现.例如,有:

• Data.PriorityQueue.FingerTree(关于hackage的fingertree- 0.0.1.0)
• Data.PurePriorityQueue(在hackage上的pure-priority-queue-0.14中)

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

• Data.Heap(在hackage的堆中1.0.0)

它定义了纯功能堆数据结构,从中可以轻松地创建优先级队列..还有

• Data.Heap(haaps -0.2 on hackage)
• Data.MeldableHeap(在haldage上的meldable-heap-2.0.3中)

它们都使用Brodal/Okasaki数据结构实现纯功能可融合堆,我认为这类似于非纯函数域中的二项式堆数据结构.

(哦,还有

• Data.PriorityQueue(在hackage的priority-queue-0.2.2中)

它的功能对我来说不清楚,但它似乎与monad相关的构建优先级队列,并且无论如何似乎都建立在Data.Map之上.在这个问题中,我关注纯粹的功能优先级队列,所以我认为priority-queue-0.2.2包是无关紧要的.但如果我错了,请纠正我!)

对于我正在构建的项目,我需要一个纯函数优先级队列数据结构.我想知道是否有人可以提供任何智慧的话语,因为我决定了hackage提供的财富的尴尬.特别:

1. 假设我想在纯函数/不可变表示中执行除传统优先级队列插入和提取最小值操作之外的功能.上面提到的包的优缺点是什么？有没有人有'愤怒'使用其中任何一个的经验？表现有哪些权衡？可靠性？其他人更广泛地使用哪种？(使用这些可能会使我的代码更容易让其他人阅读,因为他们更有可能熟悉该库.)在他们之间作出决定之前还有其他我应该知道的事情吗？
2. 如果我也想要有效合并优先级队列,那么呢？(我不赞成这个项目,但我想添加这个,但会使SO问题对未来的读者更有用.)
3. 我错过了还有其他优先级队列包吗？

Answer 1

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

Louis Wassermann(也写了pqueue包)在MonadReader(第16期)中有一篇非常好的文章.在他的文章中,路易斯提供了各种不同的优先级队列实现,并且还包括每种算法的复杂性. 作为一些优先级队列内部的简单性的一个突出的例子,他包括一些很酷的小实现.我最喜欢的一个(取自他的文章):

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 这里.