4.3 Tas
157
Proposition 4.17 Sous le modèle où tous les tas de même taille sont
équiprobables, et lorsque n = 2 L , les valeurs moyennes du nombre
d’échanges ξ et du nombre de comparaisons η pour reconstruire un tas après
suppression de son minimum valent asymptotiquement, pour n → +∞,
E[ξ ] = L − 1 + o(1);
E[η] = 2L − 1 + o(1).
Le comportement plus fin de η et ξ , ainsi que leur étude lorsque n n’est pas
une puissance de 2, semblent être des problèmes ouverts.
Nous l’avons vu en section 2.2.2, il existe deux lois sur
l’ensemble des tas de taille fixée, qui peuvent être associées aux deux
algorithmes classiques de construction d’un tas : soit toutes les clés sont
connues dès le départ, le tas est construit avec l’algorithme de Floyd, et les tas
de taille n sont alors équiprobables (c’est le cas que nous avons traité au début
de cette section) ; soit les clés sont ajoutées une par une avec l’algorithme
de Williams, et si nous supposons que les clés de 1 à n arrivent selon une
permutation choisie uniformément dans S n , la loi P W sur l’ensemble des tas
de taille n n’est plus uniforme (cf. la section 2.2.2). C’est ce dernier cas que
nous abordons maintenant.
Lorsque l’algorithme de Williams est utilisé pour construire le tas par
insertions successives des clés, le coût global de construction est donné par le
résultat suivant, dû à Hayward et McDiarmid [127, Th. 1.3] (cf. aussi Bollobas
et Simon [30] et Frieze [110]).
Proposition 4.18 En supposant tous les tas de même taille n équiprobables,
les nombres d’échanges ξ et de comparaisons η, effectués par l’algorithme de
Williams de la section A.6.3 pour construire un tas de taille n, sont tels que,
lorsque n → +∞,
E[ξ ]
n
→ w
et
E[η]
n
→ 1 + w,
où w est une constante comprise entre 1,2778. . . et 1,2994. . . De plus, pour
tout ε > 0,
P
E[ξ ]
n
− w
> ε
= o
e
−
n
log 4 n
.
157
Proposition 4.17 Sous le modèle où tous les tas de même taille sont
équiprobables, et lorsque n = 2 L , les valeurs moyennes du nombre
d’échanges ξ et du nombre de comparaisons η pour reconstruire un tas après
suppression de son minimum valent asymptotiquement, pour n → +∞,
E[ξ ] = L − 1 + o(1);
E[η] = 2L − 1 + o(1).
Le comportement plus fin de η et ξ , ainsi que leur étude lorsque n n’est pas
une puissance de 2, semblent être des problèmes ouverts.
Nous l’avons vu en section 2.2.2, il existe deux lois sur
l’ensemble des tas de taille fixée, qui peuvent être associées aux deux
algorithmes classiques de construction d’un tas : soit toutes les clés sont
connues dès le départ, le tas est construit avec l’algorithme de Floyd, et les tas
de taille n sont alors équiprobables (c’est le cas que nous avons traité au début
de cette section) ; soit les clés sont ajoutées une par une avec l’algorithme
de Williams, et si nous supposons que les clés de 1 à n arrivent selon une
permutation choisie uniformément dans S n , la loi P W sur l’ensemble des tas
de taille n n’est plus uniforme (cf. la section 2.2.2). C’est ce dernier cas que
nous abordons maintenant.
Lorsque l’algorithme de Williams est utilisé pour construire le tas par
insertions successives des clés, le coût global de construction est donné par le
résultat suivant, dû à Hayward et McDiarmid [127, Th. 1.3] (cf. aussi Bollobas
et Simon [30] et Frieze [110]).
Proposition 4.18 En supposant tous les tas de même taille n équiprobables,
les nombres d’échanges ξ et de comparaisons η, effectués par l’algorithme de
Williams de la section A.6.3 pour construire un tas de taille n, sont tels que,
lorsque n → +∞,
E[ξ ]
n
→ w
et
E[η]
n
→ 1 + w,
où w est une constante comprise entre 1,2778. . . et 1,2994. . . De plus, pour
tout ε > 0,
P
E[ξ ]
n
− w
> ε
= o
e
−
n
log 4 n
.