Est-il un standard de Java mise en œuvre d'un tas de Fibonacci?

Je regardais les différents types de tas de structures de données.

Le tas de Fibonacci semble avoir le meilleur pire des cas, la complexité de (1) l'insertion d'une, (2) la suppression et (2) de trouver le minimum de l'élément.

J'ai constaté qu'en Java il existe une classe PriorityQueue qui est un équilibre tas binaire. Mais pourquoi ils n'utilisent pas un tas de Fibonacci?

Aussi, est-il de la mise en œuvre d'un tas de Fibonacci dans java.util?

Merci!

  • java collections offrent la plus courante des structures de données. Je suppose tas de Fibonacci est plus spécialisé, ou peut-être que c'est à l'aide de plus de mémoire.
  • quel est le problème avec le tas de Fibonacci de toute façon? o.o
InformationsquelleAutor Phil | 2011-06-08
  1. 46

    Non, le standard de Java API collections ne contiennent pas la mise en œuvre d'un tas de Fibonacci. Je ne suis pas sûr pourquoi, mais je crois que c'est parce que tandis que les tas de Fibonacci sont asymptotiquement grand dans la méthode de l'amortissement sens, ils ont d'énormes facteurs constants dans la pratique. Les collections cadre aussi ne pas avoir un tas binomial, ce qui serait un autre bon tas d'inclure.

    Totalement éhontée auto-plug, j'ai une mise en œuvre d'un tas de Fibonacci en Java sur mon site web personnel. Je ne suis pas sûr de savoir comment elle sera utile, mais si vous êtes curieux de voir comment il fonctionne, je pense que ça pourrait être un bon point de départ.

    Espérons que cette aide!

    • Merci beaucoup. Votre application a l'air bien fait et bien documenté avec de nombreuses explications. Je vais jeter un oeil à ce.
    • certaines (unité) pour les tests? aussi la licence sous laquelle est le code?
    • Wow, j'allais écrire mon propre pour le plaisir, mais la tienne est tellement agréable!
    • Comment est-il accomplir dans la réalité? Le tas de Fibonacci semble avoir beaucoup de surcharge de la mémoire.
    • Des tas de Fibonacci sont notoirement lent, dans la pratique, c'est précisément pour la raison que vous avez mentionnés.
    InformationsquelleAutor templatetypedef
  2. 5

    Mais pourquoi ils n'utilisent pas un tas de Fibonacci?

    Probablement parce que ces tas beaucoup plus de frais généraux par l'entrée de clés binaires.

    Aussi, est-il de la mise en œuvre de Fibonacci tas en Java.util?

    Non, mais

    1. Il est graphmaker de Nathan Fiedler - GPL et avec une bonne la couverture de test,
      mais regarder dans ce joli blog à ce sujet et à propos de
      les problèmes de fibonacci impl peut avoir. Dans ce post, beaucoup d'autres Java implémentation sont référencés.
    2. Il y a un peu de code avec des tests unitaires ici
    3. La JGraphT projet (aussi Nathan Fiedler) et aussi avec des (légères) tests mais LGPL.
    4. Dernier mais non le moins, il est Neo4j - GPL - pas de tests.
    InformationsquelleAutor Karussell
  3. 1

    Mais pourquoi ils n'utilisent pas un tas de Fibonacci?

    Je pense que la principale raison est parce que le tas de Fibonacci ne peut que l'aider dans le cas où vous avez beaucoup plus de decreaseKey opération connecté à un extractMin opération. Par exemple, lorsque vous l'utilisez avec l'algorithme de Dijkstra.

    Aussi, est-il de la mise en œuvre de Fibonacci tas en Java.util?

    Il n'y a pas de mise en œuvre en Java.util, mais j'ai fait quelques expériences sur ce sujet à l'aide de programmes open-source existants versions du tas de Fibonacci. Vous pouvez le trouver sur mon blog ou sur le projet de dépôt GitHub.

    • Pouvez-vous préciser votre réponse pour la première question
    • Bien sûr, je peux. Fibonacci Tas a une supériorité sur le Tas Binaire sur l'exécution de decreaseKey et les opérations d'insertion, il a aussi la complexité en même temps pour extractMin, mais cette opération prend beaucoup plus de temps pour FH que BH, parce que c'est la consolidation de l'intérieur de l'arbre de la forêt. Donc, si vous avez très peu de decreaseKey alors il est plus lent que la normale Tas Binaire. Pour certains graphiques, qui est le cas pour l'algorithme de Dijkstra.
    InformationsquelleAutor gabormakrai