48
2 Aléa sur les arbres
Fig. 2.4 Les deux tas possibles sur {1, 2, 3}. Sous le modèle des permutations uniformes et en
construisant le tas par l’algorithme de Floyd, le premier tas est obtenu par les permutations 123,
213 et 321, le second par les permutations 132, 231 et 312 ; les deux tas sont équiprobables.
Avec l’algorithme de Williams, le premier tas est obtenu par les clés entrées dans l’ordre des
permutations 123 et 213, et le second tas par les permutations 132, 231, 312 et 321 ; le second tas
a donc une probabilité double du premier
Construction statique : l’algorithme de Floyd (cf. l’article original [106] et
la présentation que nous en faisons dans l’annexe A.6.3) construit un tas à partir
d’un ensemble de clés donné : dans cette situation nous partons d’un tableau de n
clés, i.e., d’un arbre parfait marqué (nous renvoyons à l’implémentation d’un arbre
parfait dans un tableau, présentée en annexe A.6.3), et construisons la structure de
tas « de bas en haut », des feuilles vers la racine.
Se pose alors la question de savoir combien d’arbres parfaits marqués donnent
le même tas : ce nombre nous est déjà connu, c’est la formule d’équerre de la
proposition 1.25, et il dépend uniquement de la forme de l’arbre parfait, i.e., de
sa taille n. Il est donc le même pour tous les tas de taille donnée n : chaque tas
de taille n est obtenu en partant de plusieurs tableaux initiaux, et le nombre de ces
tableaux ne dépend pas du tas. Si la distribution initiale sur S n est uniforme, les
tas construits avec l’algorithme de Floyd suivent eux aussi une loi uniforme P F sur
l’ensemble des tas de taille n.
Construction dynamique : l’algorithme de Williams (cf. l’article original [250] et la présentation en annexe A.6.3) permet d’insérer une clé dans un tas ;
en l’utilisant pour insérer successivement n clés dans un tas initialement vide, dans
l’ordre correspondant à une permutation de S n , nous construisons ainsi un tas de
taille n. Tout tas apparaît au moins une fois, lorsque l’ordre hiérarchique 2 des clés
du tas est aussi celui donné par la permutation d’entrée.
En partant d’une loi uniforme sur S n , les tas ainsi construits suivent une loi
P W qui n’est plus uniforme sur l’ensemble des tas de taille n ; cf. Doberkat [63].
Nous pouvons par exemple constater (cf. la figure 2.4) que, dès n = 3, les deux
tas possibles ont des probabilités respectives sous P W égales à 1/3 et 2/3. Cette loi
est mal connue, le seul début d’étude semble se trouver dans l’article de Porter et
Simon [212], et une question ouverte serait de la caractériser.
2 L’ordre hiérarchique correspond à un parcours par niveaux croissants de l’arbre, et de gauche à
droite à chaque niveau ; cf. annexe A.1.3.
2 Aléa sur les arbres
Fig. 2.4 Les deux tas possibles sur {1, 2, 3}. Sous le modèle des permutations uniformes et en
construisant le tas par l’algorithme de Floyd, le premier tas est obtenu par les permutations 123,
213 et 321, le second par les permutations 132, 231 et 312 ; les deux tas sont équiprobables.
Avec l’algorithme de Williams, le premier tas est obtenu par les clés entrées dans l’ordre des
permutations 123 et 213, et le second tas par les permutations 132, 231, 312 et 321 ; le second tas
a donc une probabilité double du premier
Construction statique : l’algorithme de Floyd (cf. l’article original [106] et
la présentation que nous en faisons dans l’annexe A.6.3) construit un tas à partir
d’un ensemble de clés donné : dans cette situation nous partons d’un tableau de n
clés, i.e., d’un arbre parfait marqué (nous renvoyons à l’implémentation d’un arbre
parfait dans un tableau, présentée en annexe A.6.3), et construisons la structure de
tas « de bas en haut », des feuilles vers la racine.
Se pose alors la question de savoir combien d’arbres parfaits marqués donnent
le même tas : ce nombre nous est déjà connu, c’est la formule d’équerre de la
proposition 1.25, et il dépend uniquement de la forme de l’arbre parfait, i.e., de
sa taille n. Il est donc le même pour tous les tas de taille donnée n : chaque tas
de taille n est obtenu en partant de plusieurs tableaux initiaux, et le nombre de ces
tableaux ne dépend pas du tas. Si la distribution initiale sur S n est uniforme, les
tas construits avec l’algorithme de Floyd suivent eux aussi une loi uniforme P F sur
l’ensemble des tas de taille n.
Construction dynamique : l’algorithme de Williams (cf. l’article original [250] et la présentation en annexe A.6.3) permet d’insérer une clé dans un tas ;
en l’utilisant pour insérer successivement n clés dans un tas initialement vide, dans
l’ordre correspondant à une permutation de S n , nous construisons ainsi un tas de
taille n. Tout tas apparaît au moins une fois, lorsque l’ordre hiérarchique 2 des clés
du tas est aussi celui donné par la permutation d’entrée.
En partant d’une loi uniforme sur S n , les tas ainsi construits suivent une loi
P W qui n’est plus uniforme sur l’ensemble des tas de taille n ; cf. Doberkat [63].
Nous pouvons par exemple constater (cf. la figure 2.4) que, dès n = 3, les deux
tas possibles ont des probabilités respectives sous P W égales à 1/3 et 2/3. Cette loi
est mal connue, le seul début d’étude semble se trouver dans l’article de Porter et
Simon [212], et une question ouverte serait de la caractériser.
2 L’ordre hiérarchique correspond à un parcours par niveaux croissants de l’arbre, et de gauche à
droite à chaque niveau ; cf. annexe A.1.3.