¿Hay una implementación Java estándar de un montón de Fibonacci?

Estaba mirando el diferente tipo de estructuras de datos de montón.¿Hay una implementación Java estándar de un montón de Fibonacci?

El montón Fibonacci parece tener la mejor complejidad de peor caso para (1) inserción, (2) eliminación y (2) encontrar el elemento mínimo.

He encontrado que en Java hay una clase PriorityQueue que es un montón binario balanceado. 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!

Fuente

2011-06-08 Phil

Las colecciones de Java proporcionan solo las estructuras de datos más comunes. Supongo que Fibonacci Heap es más especializado, o tal vez está usando más memoria. –

@James, ¿qué importa eso con el montón de Fibonacci de todos modos? o.o – ignis

No, la API de colecciones de Java estándar 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 autoenchufe totalmente desvergonzado, tengo an implementation of a Fibonacci heap in Java on my personal website. 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!

Fuente

2011-06-08 03:24:43 templatetypedef

Muchas gracias. Su implementación se ve bien hecha y bien documentada con muchas explicaciones. Voy a echar un vistazo a esto. – Phil

¿hay algunas pruebas (de unidad)? también que licencia es el código? – Karussell

¡Guau, iba a escribir la mía para divertirme, pero la tuya es muy agradable! – Andy

¿Pero por qué no usaron un montón de Fibonacci?

Probablemente porque esos montones tienen mucha más sobrecarga por entrada que las teclas binarias.

Además, ¿hay una implementación de Fibonacci Heap en Java.util?

No, pero

No es graphmaker de Nathan Fiedler - GPL y con buena test coverage, pero tienen una mirada en this nice blog post al respecto y sobre problemas de un Fibonacci impl puede tener. En esta publicación se hace referencia a muchas otras implementaciones de Java.
Hay algo de código con la unidad de prueba here
El JGraphT project (también Nathan Fiedler) y también con (algunos menores) tests pero LGPL.
Por último pero no menos importante es Neo4j - GPL - sin pruebas.

Fuente

2012-01-15 15:15:15 Karussell

¿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 tiene mucho más operación de disminución de la tecla conectada a una operación de extracciónMin. 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 las versiones de código abierto existentes del montón de Fibonacci. Puede encontrarlo on my blog o en el project's GitHub repository.

Fuente

2015-02-12 18:56:10 gabormakrai

¿Puede explicar su respuesta a la primera pregunta? – arunmoezhi

Por supuesto que puedo. Fibonacci Heap tiene superioridad sobre Binary Heap al ejecutar las operaciones de lowerkey e inserción, también tiene la misma complejidad de tiempo para extractMin, pero esta operación toma mucho más tiempo para FH que BH, porque está consolidando el bosque de árbol interno. Entonces, si tiene un número muy bajo de decreasKey, entonces es más lento que el Binary Heap normal. Para algunos gráficos especiales, ese es el caso del algoritmo de Dijkstra. – gabormakrai

¿Hay una implementación Java estándar de un montón de Fibonacci?

Respuesta

Cuestiones relacionadas