Existe-t-il une implémentation de structure de données de file d'attente prioritaire dans la bibliothèque standard de Ruby?
La bibliothèque standard de Ruby a-t-elle une implémentation de file d'attente prioritaire?
5 réponses
Il y a aussi https://rubygems.org/gems/PriorityQueue , qui fonctionne toujours 1.9 même s'il n'a pas été changé depuis 2005.
Cela fonctionne bien d'après ce que j'ai essayé, il y a un benchmark, et c'est bien documenté. Je ne pourrais pas dire cela pour PriorityQueue et Heap des algorithmes (ce qui ne semble pas permettre de changer facilement la clé pour une valeur donnée).
Vient de publier une extension ruby (en C++) implémentant des files d'attente prioritaires, c'est l'ordre des grandeurs plus rapide que les implémentations basées sur ruby. Voir https://rubygems.org/gems/priority_queue_cxx.
Il y a le rubygem de longue date rbtree qui fournit ce type de fonctionnalité. C'est une implémentation de Arbre Rouge-Noir.
De plus, il existe une implémentation ruby pure rbtree-pure .