Tas binomial
From Wikipedia, the free encyclopedia
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(log 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, c'est-à-dire une file à priorités permettant des opérations de fusion.
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 2k nœuds, et a pour hauteur 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é 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, , 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 indexé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.
