Tas binomial

En informatique, un tas binomial est une structure de données assez proche du tas binaire, mais qui permet aussi de fusionner deux tas rapidement. Ainsi, il supporte les opérations suivantes, toutes en O(ln n):

• Insérer un nouvel élément au tas
• Trouver l'élément de plus petite clé
• Effacer du tas l'élément de plus petite clé
• Diminuer la clé d'un élément donné
• Effacer un élément donné du tas
• Fusionner deux tas en un seul

Le tas binomial est donc une implémentation du type abstrait tas fusionnable, ie une file à priorités permettant des opérations de fusion.

Notion d'arbre binomial

Un tas binomial est en fait un ensemble d'arbres binomiaux (à comparer avec un tas binaire, qui correspond à un unique arbre binaire). Un arbre binomial est défini récursivement comme suit:

• L'arbre binomial d'ordre 0 est un simple nœud
• L'arbre binomial d'ordre k possède une racine de degré k et ses fils sont racines d'arbre binomiaux d'ordre k-1, k-2, ..., 2, 1, 0 (dans cet ordre)

Un arbre binomial d'ordre k peut aussi être construit à partir de deux arbres d'ordre k-1 en faisant de l'un des deux le fils le plus à gauche de la racine de l'autre. Un arbre binomial d'ordre k possède 2^k nœuds, et a pour taille k.

Des variantes d'arbres binomiaux sont aussi utilisées pour construire les tas de Fibonacci.

Structure des tas binomiaux

Un tas binomial est implémenté en tant qu'ensemble d'arbres binomiaux satisfaisant aux propriétés des tas binomiaux:

• Chaque arbre binomial du tas possède une structure ordonnée en tas: la clé de chaque nœud est supérieure ou égale à celle de son parent.
• Pour tout j entier naturel, il existe au plus un tas binomial d'ordre j.

La première propriété nous indique que la racine de chaque arbre binomial possède la plus petite clé de l'arbre. La seconde propriété implique qu'un tas binomial contenant n éléments consiste en au plus ln n + 1 arbres binomiaux.. En fait, le nombre et les ordres de ces arbres est déterminé de manière unique par le nombre n d'éléments: chaque tas binomial correspond au bit 1 dans l'écriture binaire du nombre n. Par exemple, 13 correspond à 1101 en binaire, 2³ + 2² + 2⁰, et donc le tas binomial à 13 éléments consistera en 3 arbres binomiaux d'ordres respectifs 3, 2 et 0 (cf. figure ci-dessous) Les racines des arbres binomiaux sont stockées dans une liste indicée par l'ordre des arbres.

Exemple de tas binomial contenant des éléments de clés 1, 2, ..., 13. Le tas consiste en 3 arbres binomiaux d'ordre 0, 2, et 3.

Implémentation des opérations

L'opération de fusion de deux tas est sans doute la plus intéressante et est réutilisée dans la plupart des autres opérations. Les listes de racines des deux tas sont parcourues simultanément, de même que pour le tri fusion. Si seul un des deux tas contient un arbre d'ordre j, celui-ci est ajouté au tas fusionné. Si les deux tas contiennent un arbre d'ordre j, les deux arbres sont fusionnés en un arbre d'ordre j+1 en respectant la structure de tas (la plus grande des deux racines devient fille de la plus petite). Notez que l'on peut avoir besoin de fusionner cet arbre avec un arbre d'ordre j+1 présent dans un des deux tas initiaux. Durant l'algorithme, nous examinons au plus 3 arbres de chaque ordre (deux provenant des deux tas que nous fusionnons et un formé à partir de deux arbres plus petits). Or l'ordre maximal d'un arbre est ln n et donc la complexité de la fusion est en O(ln n).

Pour insérer un nouvel élément dans un tas on crée simplement un nouveau tas contenant uniquement cet élément que nous fusionnons ensuite avec le tas initial, et ce en O(ln n).

Pour trouver le plus petit élément du tas, nous avons seulement besoin de trouver le minimum parmi les racines des arbres binomiaux (au nombre maximal de ln n), ce qui ce fait une fois de plus en O(ln n).

Pour supprimer le plus petit élément du tas, on trouve tout d'abord cet élément pour l'enlever de son arbre binomial : on obtient alors une liste de ses sous-arbres, que l'on transforme en un autre tas binomial, ensuite fusionné au tas précédent.

Quand nous diminuons la clé d'un élément, elle peut devenir plus petite que celle de son père, violant l'ordre en tas de l'arbre. Dans ce cas, nous échangeons l'élément avec son père, voire avec son grand-père, et ainsi de suite jusqu'à ce que l'arbre soit de nouveau ordonné en tas. Chaque arbre binomial ayant pour taille maximale ln n, l'opération est en O(ln n).

Enfin pour supprimer un élément, on lui donne pour clé moins l'infini (plus petite que toutes les autres clés...) puis on supprime le plus petit élément du tas, c’est-à-dire lui-même.

Références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Binomial heap » (voir la liste des auteurs)
• (en) Thomas H. Cormen (en), Charles E. Leiserson (en) et Ronald L. Rivest, Introduction to Algorithms (en), 1990, MIT Press (ISBN 0-262-03141-8).
• (en) J. Vuillemin, « A data structure for manipulating priority queues », dans Communications of the ACM 21(1978), 309-314.

Voir aussi

Articles connexes

• Tas
• Tas de Fibonacci

Lien externe

(en) Une simulation Java d'un tas binomial