Pseudocódigo para la cola Brodal

12

Estoy tratando de encontrar más recursos con respecto al montón de Brodal . Todo lo que encontré es una implementación haskell del montón Brodal-Okasaki , pero creo que son montones sesgados , ¿es esto correcto? Además, soy analfabeta en Haskell, así que eso no ayuda mucho. ¿Alguien tiene (o sabe) una implementación de cola Brodal en pseudocódigo, C, C ++, Python?

También corrija si mis suposiciones anteriores son incorrectas.

research data-structures Kimvais
fuente
3
¿Está buscando implementar específicamente la cola Brodal, o está buscando una implementación eficiente de una cola prioritaria? Brodal mencionó en la conclusión de su artículo que no son prácticos sin alguna investigación adicional en el área. Su artículo ha sido ampliamente citado, ¿tal vez algo útil? La Introducción a los algoritmos de CLR tiene una sección sobre colas de prioridad, pero hace referencia a un trabajo mucho más temprano en colas de prioridad.
Jay Elston
2
La cola Brodal original usa una asignación destructiva, por lo que la versión de Haskell debe tener algunas modificaciones.
Fred Foo

Respuestas:

2

La implementación de Haskell se basa en el montón funcional Brodal-Okasaki y tiene razón, es una variación de montones sesgados. El documento está escrito muy claramente, por lo que sería un buen recurso.

En cuanto a la implementación, también hay una implementación en Scala como parte de la biblioteca scalaz.

maayank
fuente
1

Esta es una respuesta parcial ya que aún no he descubierto cómo traducir el código en algo que no sea Haskell. La razón por la que puedo decir que tienen que usar Haskell es que Haskell es vago. El montón Brodal-Okasaki debe ser implementado de manera perezosa por el periódico. Entonces, lo que necesitaría es una forma de proporcionar esa funcionalidad a otro idioma junto con cualquier otro requisito (como estructuras de datos puramente funcionales) que pueda necesitar el BO Heap.

Ingeniero mundial
fuente