Tas de Fibonacci

En informatique, un tas de Fibonacci est une structure de données similaire au tas binomial, mais avec un meilleur temps d'exécution amorti. Les tas de Fibonacci ont été conçus par Michael L. Fredman et Robert E. Tarjan en 1984 et publiés pour la première fois dans un journal scientifique en 1987. Les tas de Fibonacci sont utilisés pour améliorer le temps asymptotique de l'algorithme de Dijkstra, qui calcule les plus courts chemins dans un graphe, et de l'algorithme de Prim, qui calcule l'arbre couvrant de poids minimal d'un graphe. Le nom de tas de Fibonacci vient des nombres de Fibonacci, qui sont utilisés pour calculer son temps d'exécution. En particulier, les opérations insertion, trouver le minimum, décroître une clé, et union ont toutes un coût amorti constant. Les opérations supprimer et supprimer le minimum ont un coût amorti en O(log n). C'est-à-dire qu'en partant d'une structure vide, n'importe quelle séquence de a opérations du premier groupe et b opérations du second groupe prendrait un temps O(a + (b log n)). Dans un tas binomial, une telle séquence d'opérations prendrait un temps O((a + b)(log n)). Il devient donc plus intéressant d'utiliser un tas de Fibonacci plutôt qu'un tas binomial lorsque b est asymptotiquement plus petit que a. Un tas de Fibonacci est un ensemble d'arbres satisfaisant la propriété de tas-minimum, c'est-à-dire que la clé d'un fils est toujours supérieure ou égale à la clé de son père. Ceci implique que la clé minimum est toujours à la racine d'un des arbres. La structure des tas de Fibonacci est plus flexible que celle des tas binomiaux, en ce sens qu'elle permet à quelques opérations d'être exécutées de manière « paresseuse », en reportant le travail sur des opérations ultérieures. Par exemple, l'union de deux tas est effectuée simplement en concaténant les deux listes d'arbres, et l'opération de diminution de clé coupe parfois un nœud de son père pour former un nouvel arbre. Cependant, à un moment donné il est nécessaire d'introduire un certain ordre dans la structure du tas de manière à obtenir le temps d'exécution voulu.