serie - ¿Hay una implementación Java estándar de un montón de Fibonacci?
serie fibonacci algoritmo (3)
Estaba viendo el diferente tipo de estructuras de datos de montón.
El montón de Fibonacci parece tener la mejor complejidad de peor caso para (1) inserción, (2) eliminación y (2) búsqueda del elemento mínimo.
He descubierto que en Java hay una clase PriorityQueue que es un montón binario equilibrado. Pero ¿por qué no usaron un montón de Fibonacci?
Además, ¿hay una implementación de un montón de Fibonacci en java.util ?
¡Gracias!
Pero ¿por qué no usaron un montón de Fibonacci?
Creo que la razón principal es porque el montón de Fibonacci solo puede ayudar en el caso cuando tienes muchas más operaciones de disminución de teclas conectadas a una operación de extracción en miniatura. Por ejemplo, cuando lo está utilizando con el algoritmo de Dijkstra.
Además, ¿hay una implementación de Fibonacci Heap en Java.util?
No hay implementación en Java.util, pero hice algún experimento sobre este tema utilizando versiones de código abierto existentes del montón de Fibonacci. Puedes encontrarlo en mi blog o en el repositorio de GitHub del proyecto .
Pero ¿por qué no usaron un montón de Fibonacci?
Probablemente porque esos montones tienen mucho más sobrecarga por entrada que las teclas binarias.
Además, ¿hay una implementación de Fibonacci Heap en Java.util?
No pero
- Hay un graphmaker de graphmaker de Nathan Fiedler - GPL y con buena cobertura de prueba , pero eche un vistazo a esta agradable publicación de blog sobre esto y sobre los problemas que puede tener una implementación de fibonacci. En esta publicación se hace referencia a muchas otras implementaciones de Java.
- Hay algún código con pruebas unitarias here
- El proyecto JGraphT (también Nathan Fiedler) y también con (algunas tests menores) pero LGPL.
- Por último, pero no menos importante, está Neo4j - GPL - sin pruebas.
No, la API de colecciones estándar de Java no contiene una implementación de un montón de Fibonacci. No estoy seguro de por qué esto es así, pero creo que es porque aunque los montones de Fibonacci son asintóticamente grandes en un sentido amortizado, tienen factores constantes en la práctica. El marco de colecciones tampoco tiene un montón binomial, que sería otro buen montón para incluir.
Como un autoencaje totalmente desvergonzado, tengo una implementación de un montón de Fibonacci en Java en mi sitio web personal . No estoy seguro de lo útil que será, pero si tiene curiosidad por ver cómo funciona, creo que podría ser un buen punto de partida.
¡Espero que esto ayude!