Есть ли реализация стандартной структуры данных в стандартной библиотеке Ruby?

Question

Есть ли в стандартной библиотеке Ruby реализация очереди с приоритетами?

Answer 1

Нет, но есть один в Алгоритмы и контейнеры Канвей Ли, проект GSoC 2008 .

Answer 2

Существует также https://rubygems.org/gems/PriorityQueue,, который все еще работает 1,9, даже если он не изменился с 2005 года.

Он хорошо работает из того, что я пробовал, есть эталонный тест, и он хорошо документирован,Я мог бы не сказать, что для алгоритмов PriorityQueue и Heap (которые, кажется, не позволяют легко изменить ключ для данного значения).

Answer 3

Только что опубликовано расширение ruby ​​(в C ++), реализующее приоритетные очереди, оно на порядок быстрее, чем реализации на основе ruby. Смотри https://rubygems.org/gems/priority_queue_cxx.

Answer 4

В RubyGems есть реализация skewheap , если вам интересно.

Answer 5

Существует давний rubygem rbtree , который обеспечивает этот тип функциональности. Это реализация Красно-черного дерева .

Кроме того, существует чистая реализация ruby ​​ rbtree-pure .