Существует ли реализация структуры данных очереди приоритетов в стандартной библиотеке Ruby?

Ответ 1

Нет, но там один в Kanwei Li Алгоритмы и контейнеры GSoC 2008 проект.

Ответ 2

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

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

Ответ 3

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

Ответ 4

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

Ответ 5

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

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