开发者

Is there priority queue data structure implementation in Ruby's standard library?

开发者 https://www.devze.com 2023-01-25 06:53 出处：网络

Does Ruby\'s standard library ha开发者_如何学Gove a priority queue implementation?Nope, but there\'s one in Kanwei Li\'s Algorithms and Containers GSoC 2008 project.There is also https://rubygems.org/

相关专题：data-structures priority-queue ruby

Does Ruby's standard library ha开发者_如何学Gove a priority queue implementation?

Nope, but there's one in Kanwei Li's Algorithms and Containers GSoC 2008 project.

There is also https://rubygems.org/gems/PriorityQueue, which still works 1.9 even though it wasn't changed from 2005.

It works well from what I tried, there is a benchmark, and it is well documented. I might not say that for algorithms's PriorityQueue and Heap (which does not seems to allow to change the key for a given value easily).

Just published a ruby extension (in C++) implementing priority queues, it's order of magnitudes faster than ruby based implementations. See https://rubygems.org/gems/priority_queue_cxx.

There is a skewheap implementation in RubyGems, if you're interested.

There is the long standing rubygem rbtree which provides this type of functionality. It is an implementation of Red-Black Tree.

Additionally, there is a pure ruby implementation rbtree-pure.