Ruby的标准库中有优先级队列数据结构实现吗？

Question

Ruby 的标准库有优先级队列实现吗？

Answer 1

没有，但是在Kanwei Li 的算法和容器 GSoC 2008 项目中有一个。

Answer 2

刚刚发布了一个实现优先级队列的 ruby 扩展（C++ 语言），它比基于 ruby 的实现快了几个数量级。请参阅https://rubygems.org/gems/priority_queue_cxx。

Answer 3

还有 https://rubygems.org/gems/PriorityQueue，尽管它与 2005 年相比没有改变，但它仍然可以在 1.9 版本中使用。

从我的尝试来看，它运行良好，有一个基准，并且有很好的文档记录。我可能不会这么说，对于算法的 PriorityQueue 和 Heap（这似乎不允许轻松更改给定值的键）。

Answer 4

如果您感兴趣，RubyGems 中有一个 skewheap 实现。

Answer 5

长期存在的 rubygem rbtree 提供了这种类型的功能。它是红黑树的实现。

此外，还有一个纯 ruby 实现rbtree-pure。