Tas binomial

Un article de Wikipédia, l'encyclopédie libre.

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.

[modifier] 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.

[modifier] Structure des tas binomiaux

Un tas binomial est implémenté en tant qu'ensemble de tas 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, $23 + 2 2 + 2 0$ , 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 arbre binomiaux sont stockés dans une liste indicée par l'ordre des l'arbre.

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.

[modifier] 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 arbre 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 toute les autres clés...) puis on supprime le plus petit élément du tas, c’est-à-dire lui-même.

[modifier] Voir aussi

[modifier] Bibliographie

(en) Cormen, T. H.; Leiserson C. E.; & Rivest R. L. (1990) Introduction to Algorithms. MIT Press. ISBN 0-262-03141-8
(en) Vuillemin, J. (1978). A data structure for manipulating priority queues. Communications of the ACM 21, 309-314.