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(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 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. 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.