Existe-t-il une implémentation Java standard D'un tas de Fibonacci?
Je regardais les différents types de structures de données de tas.
Le tas de Fibonacci semble avoir la meilleure complexité du pire des cas pour (1) l'insertion, (2) la suppression et (2) la recherche de l'élément minimum.
J'ai trouvé qu'en Java il y a une classe PriorityQueue qui est un tas binaire équilibré. Mais pourquoi ils n'ont pas utilisé un tas de Fibonacci?
En outre, Existe-t-il une implémentation D'un tas de Fibonacci dans java.util?
Merci!
3 réponses
Non, L'API Java collections standard ne contient pas d'implémentation D'un tas Fibonacci. Je ne sais pas pourquoi c'est, mais je crois que c'est parce que si les tas de Fibonacci sont asymptotiquement grands dans un sens amorti, ils ont d'énormes facteurs constants dans la pratique. Le framework collections n'a pas non plus de tas binomial, ce qui serait un autre bon tas à inclure.
En tant qu'Auto-plug totalement éhonté, j'ai une implémentation D'un tas Fibonacci en Java sur mon personnel site web. Je ne suis pas sûr de son utilité, mais si vous êtes curieux de voir comment cela fonctionne, je pense que cela pourrait être un bon point de départ.
J'espère que cela aide!
Mais pourquoi ils n'ont pas utilisé un tas de Fibonacci?
Probablement parce que ces tas ont beaucoup plus de frais généraux par entrée que les clés binaires.
En outre, Existe-t-il une implémentation de tas Fibonacci en Java.util?
Non, mais
- Il y a graphmaker {[15] } de Nathan Fiedler-GPL et avec une bonne couverture de test , mais jetez un oeil dans Ce joli blog à propos de cela et à propos problèmes un Fibonacci impl peut avoir. Dans ce post, beaucoup d'autres implémentations Java sont référencées.
- Il y a du code avec des tests unitaires ici
- le projet jgrapht (également Nathan Fiedler) et aussi avec (quelques tests mineurs) mais LGPL.
- , Dernier mais pas moins il y a Neo4j - GPL - pas de tests.
Mais pourquoi ils n'ont pas utilisé un tas de Fibonacci?
Je pense que la raison principale est que le tas de Fibonacci ne peut aider que dans le cas où vous avez beaucoup plus d'opération decreaseKey connectée à une opération extractMin. Par exemple, lorsque vous l'utilisez avec l'algorithme de Dijkstra.
En outre, Existe-t-il une implémentation de tas Fibonacci en Java.util?
Il N'y a pas d'implémentation en Java.util, mais j'ai fait quelques expériences sur ce sujet en utilisant versions open-source existantes du tas Fibonacci. Vous pouvez le trouver sur mon blog ou sur du projet GitHub.