Haskell中优先级队列实现的比较
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 (优先级-队列-0.2.2)
在我看来，它的功能不太清楚，但它似乎是连接到monad的相关的构建优先级队列，而且它似乎是构建在Data.Map之上的。在这个问题中，我关注的是纯功能优先级队列，因此我认为优先级队列-0.2.2包与此无关。但如果我错了，请纠正我！)
对于我正在构建的项目，我需要一个纯功能优先级队列数据结构。我在想，当我在黑客提供的财富的尴尬之间做出选择时，是否有人能提供一些智慧的话语。具体地说：
- 假设除了传统的优先级队列插入和提取-min操作之外，我希望在纯功能/不变的表示中实现do功能。上述软件包的优缺点是什么？有没有人有使用“愤怒”的经验？性能的权衡是什么？可靠性？哪些被其他人使用得更广泛？(使用这些代码可能使其他人更容易阅读我的代码，因为它们更有可能熟悉库。)在他们之间做出决定之前，还有什么我应该知道的吗？
- 如果我也希望高效地合并优先级队列，那么怎么办？(我不支持这个项目，但我想加入这个问题，但会让这个问题对未来的读者更有用。)
- 还有其他优先级队列包我错过了吗？
回答 1
Stack Overflow用户
发布于 2011-08-08 10:14:51
在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有一个特别好的界面。我想这是最早的实现之一，并在本论文中很好地被罗尔夫·辛泽所覆盖。它可能不是最有效率和最彻底的执行，但到目前为止，它已经满足了我的所有需要。
MonadReader (第16期)中有一篇非常好的文章，作者是Louis (他还编写了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]一些优先级队列实现的基准可以在这里中找到，也可以在haskell.org 这里上的一个相当有趣的线程中找到。
https://stackoverflow.com/questions/6976559
复制相似问题
腾讯云开发者
