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.

Structure d'un tas de Fibonacci

Figure 1. Exemple de tas de Fibonacci à trois arbres de degrés 0, 1 et 3. Trois sommets sont marqués (en bleu). Le potentiel du tas est donc 9.

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. En particulier, on garde les degrés des nœuds (c'est-à-dire leur nombre de fils) en dessous d'une valeur assez basse: chaque nœud a un degré au plus en O(log n) et la taille d'un sous-arbre d'un nœud de degré k est au moins F_k + 2, où F_k est le k^ème nombre de Fibonacci. Pour cela, on doit respecter la règle qui énonce qu'on ne peut couper au plus qu'un seul fils de chaque nœud non racine. Quand un second nœud est coupé, le nœud lui-même doit être coupé de son père pour devenir la racine d'un nouvel arbre. Le nombre d'arbres est diminué par l'opération supprimer le minimum, dans laquelle on relie les arbres.

En conséquence de cette structure flexible, certaines opérations peuvent prendre longtemps, alors que d'autres sont très rapides. En utilisant l'analyse amortie du temps d'exécution, on fait comme si les opérations très rapides prenaient un peu plus de temps qu'en réalité. On utilise ce temps « économisé » (comme dans un compte en banque) pour contrebalancer le temps réel d'exécution des opérations plus lentes. La quantité de temps économisé pour un usage ultérieur à un moment donné est mesurée par une fonction de potentiel. Le potentiel d'un tas de Fibonacci est donné par:

Potentiel = t + 2m

où t est le nombre d'arbres dans le tas de Fibonacci, et m est le nombre de nœuds marqués. Un nœud est marqué si au moins un de ses fils a été coupé depuis que ce nœud a été fait fils d'un autre nœud (aucune racine n'est marquée).

Ainsi, la racine de chaque arbre dans un tas possède une unité de temps en provision. Cette unité de temps peut être utilisée plus tard pour lier cet arbre avec un autre arbre en un coût amorti nul. Aussi, chaque nœud marqué a deux unités de temps en provision. Une unité peut être utilisée pour couper le nœud de son père. Quand c'est le cas, le nœud devient une racine et la deuxième unité de temps reste en stock dans ce nœud comme dans chaque racine.

Implémentation des opérations

Pour permettre la suppression rapide et la concaténation, les racines de tous les arbres sont liées par une liste doublement chaînée circulaire. Les fils de chaque nœud sont aussi liés par une liste du même type. Pour chaque nœud, on conserve des informations sur son nombre de fils et sur son marquage éventuel. De plus, on garde un pointeur sur la racine contenant la clé minimale.

L'opération trouver le minimum est maintenant triviale, puisqu'on garde un pointeur sur son nœud. Cette opération ne change pas le potentiel du tas, et donc le coût réel et le cout amorti sont constants. Comme mentionné plus haut, l'union est implémentée simplement en concaténant les listes des racines des arbres des deux tas. Cette opération peut être effectuée en temps constant et le potentiel ne change pas, et donc le temps amorti est encore constant. L'opération insertion crée un nouveau tas avec le seul élément à insérer, et effectue l'union avec le tas de départ. Ceci prend un temps constant, mais ici le potentiel augmente d'une unité, car le nombre d'arbres augmente. Le coût amorti est donc toujours constant.

Le tas de Fibonacci de la figure 1 après la première phase de l'extraction du minimum. Le nœud avec la clé 1 (le minimum) a été supprimé et ses fils ont été ajoutés comme arbres séparés.

L'opération extraire le minimum (de même que supprimer le minimum) opère en trois phases. D'abord, on prend la racine contenant l'élément minimum et on la supprime. Ses fils vont devenir les racines de nouveaux arbres. Si le nombre de fils était d, il faut un temps O(d) pour traiter toutes les nouvelles racines et la fonction de potentiel augmente de d-1. Donc le coût amorti de cette phase est O(d) = O(log n).

Le tas de Fibonacci de la figure 1 après la fin de l'opération extraire minimum. D'abord les nœuds 3 et 6 sont connectés, puis le résultat est connecté avec l'arbre de racine 2. Enfin, le nouveau minimum est trouvé.

Cependant, pour finir l'opération d'extraction du minimum, on doit mettre à jour le pointeur sur la racine de clé minimum. Malheureusement, il peut y avoir jusqu'à n racines à vérifier. Dans cette seconde phase, on décroît donc le nombre de racines en connectant successivement les racines de même degré. Quand deux racines u et v ont le même degré, on met celle avec la plus grande clé des deux en fils de celle ayant la plus petite clé. Cette dernière voit son degré augmenter de un. On répète ceci jusqu'à ce que chaque racine ait un degré différent. Pour trouver efficacement les arbres de même degré, on utilise un tableau de longueur O(log n) dans lequel on garde un pointeur sur une racine de chaque degré. Quand on trouve une seconde racine avec le même degré, on connecte les deux et on met à jour le tableau. Le temps d'exécution réel est en O(log n + r), où r est le nombre de racines au début de la seconde phase. À la fin, on aura au plus O(log n) racines (parce que chacune a un degré différent). En conséquence, le potentiel décroît d'au moins r − O(log n) et le coût amorti est O(log n).

Dans la troisième phase, on regarde chacune des racines restantes et on trouve le minimum, ce qui est fait en O(log n) et n'entraîne pas de variation du potentiel. Le coût amorti total de l'extraction du minimum est donc O(log n).

Le tas de Fibonacci de la figure 1 après avoir diminué la clé du nœud 9 à 0. Ce nœud ainsi que ses deux ancêtres marqués sont coupés de l'arbre dont la racine est 1 et placés comme nouvelles racines.

L'opération diminuer clé va prendre le nœud, décroître sa clé, et si la propriété de tas est violée (la nouvelle clé est plus petite que la clé de son père), le nœud est coupé de son père. Si le père n'est pas une racine, il est marqué. S'il était déjà marqué, on le coupe aussi et son père est marqué. On continue comme ceci en remontant dans l'arbre jusqu'à ce qu'on atteigne soit la racine, soit un nœud non marqué. Ce faisant on crée un certain nombre, appelons le k, de nouveaux arbres. Chacun de ces nouveaux arbres, sauf peut-être le premier, était déjà marqué mais va perdre son marquage en devenant racine. Un seul nœud peut se retrouver marqué. Donc, le potentiel décroît d'au moins k − 2. Le temps d'exécution réel de la coupe est O(k), et donc le temps amorti est constant.

Finalement, l'opération supprimer peut être implémentée facilement en mettant la valeur de la clé de l'élément à supprimer à (la plus petite valeur représentable), de manière à ce qu'elle devienne la plus petite valeur du tas entier. Il suffit alors d'appeler extraire minimum pour le supprimer. Le coût amorti de cette opération est O(log n).

Analyse du pire cas

Bien que le temps d'exécution total d'une séquence d'opérations en partant d'une structure vide soit borné par les valeurs données plus haut, quelques opérations dans la séquence (très peu) peuvent prendre un temps très long (en particulier diminuer clé, supprimer et supprimer minimum ont des temps d'exécution linéaires dans le pire cas). Pour cette raison, les tas de Fibonacci, ainsi que d'autres structures optimisées au niveau de leur coût amorti mais pas de leur pire cas, peuvent être mal appropriés à certaines applications temps réel.

Résumé des temps d'exécution

(*)Temps amorti

Références

• Fredman M. L. & Tarjan R. E. (1987). Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM 34(3), 596-615.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 20: Fibonacci Heaps, pp.476–497.

Liens externes

• (en) Applet Java simulant un tas de Fibonacci
• (en) Implémentation en C d'un tas de Fibonacci

• Portail de l’informatique