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

Question

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

• Data.PriorityQueue.FingerTree(在 fingertree-0.0.1.0 中)
• Data.PurePriorityQueue(在 pure-priority-queue-0.14 中)

这两者看起来都是纯粹的优先级队列数据结构。前者基于手指树，这是一种我不熟悉的数据结构；后者是 Data.Map 的包装器。还有

• Data.Heap(在 heap-1.0.0 中)

它定义了纯函数堆数据结构，可以轻松地创建优先级队列。 。还有

• Data.Heap(在 heaps-0.2 中)
• Data.MeldableHeap(在 meldable-heap-2.0.3 中)

两者都使用 Brodal/Okasaki 数据结构实现纯函数式可熔堆，我认为这类似于非纯函数式领域中的二项式堆数据结构。

(哦，还有

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

我不清楚它的功能，但它似乎与构建附加到 monad 的优先级队列有关，而且它似乎是构建在 Data.Map 之上的。在这个问题中，我关心的是纯功能优先级队列，所以我认为priority-queue-0.2.2包是无关紧要的。但如果我错了，请纠正我!)

我需要为我正在构建的项目提供一个纯功能的优先级队列数据结构。我想知道当我在 embarrassment of riches 之间做出决定时是否有人可以提供任何智慧之言。由 hackage 提供。具体来说:

1. 假设我想要在纯功能/不可变的演示中执行传统优先级队列插入和提取最小操作之外的功能。上述套餐的优点和缺点是什么？有人有过“愤怒地”使用它们的经验吗？性能方面的权衡是什么？可靠性？哪些被其他人更广泛地使用？ (使用这些可能会让我的代码更容易被其他人阅读，因为他们更有可能熟悉这个库。)在他们之间做出决定之前我还应该知道其他事情吗？
2. 如果我还想高效合并优先级队列，那该怎么办？ (我不喜欢这个项目，但我认为添加这个会使 SO 问题对 future 的读者更有用。)
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 有一个特别好的界面。我想这是第一个实现之一，并且在 this paper 中有很好的介绍。作者:拉尔夫·欣策。它可能不是最有效和最完整的实现，但到目前为止它已经满足了我的所有需求。

Louis Wassermann(他也编写了 issue 16 包)在 MonadReader ( pqueue ) 中有一篇非常好的文章。 Louis 在他的文章中给出了各种不同的优先级队列实现，并且还包括每种实现的算法复杂性。
作为优先级队列内部结构简单性的一个引人注目的例子，他包含了一些很酷的小实现。我最喜欢的一篇(摘自他的文章):

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]

优先级队列实现的一些基准可以在 here 找到并且在一个相当有趣的thread在 haskell.org 上 here .