92
3 Arbres, algorithmes et données
L’insertion d’une nouvelle clé dans un tas peut se faire de deux façons distinctes,
suivant que l’ensemble de toutes les clés est connu ou non. Lorsque le tas est
utilisé pour implémenter une file de priorité, par exemple, les clés arrivent puis sont
supprimées de façon dynamique, et ne sont pas toutes connues avant le début de la
construction du tas ; l’algorithme d’insertion procède en insérant le nouvel élément
comme dernière feuille du tas, puis en le faisant monter à sa place sur le chemin
allant de cette feuille vers la racine. Cet algorithme, dû à Williams, est présenté en
section A.6.3. Par contre, lorsque nous voulons trier un ensemble donné de clés en
utilisant le tri par tas, les clés peuvent être supposées toutes connues à l’avance. Il
existe alors un autre algorithme, dû à Floyd et donné lui aussi en section A.6.3, qui
permet de construire le tas de manière plus efficace que par applications répétées de
l’algorithme de Williams. Son idée de base est de partir de l’arbre parfait marqué
par les n clés, et de le rendre croissant en transformant en tas les « petits » sousarbres au niveau juste au dessus des feuilles, puis ceux dont la racine est au niveau
immédiatement supérieur, et dont les deux sous-arbres sont donc des tas, et ainsi de
suite jusqu’à remonter à la racine de l’arbre.
En ce qui concerne la suppression du minimum du tas, 18 il existe là aussi deux
algorithmes, suivant que l’on rétablit d’abord la structure d’arbre parfait puis celle
d’arbre ordonné, ou l’inverse. Le premier algorithme prend la marque de la dernière
feuille et la met à la racine de l’arbre qui redevient donc un arbre parfait, puis la fait
redescendre vers un niveau plus profond, en reconstruisant la contrainte d’ordre. Le
second algorithme travaille sur un chemin de la racine vers une feuille, en faisant
remonter à chaque niveau, dans le nœud dont la marque a été transférée au niveau
supérieur (ou ôtée dans le cas de la racine) la plus petite marque de ses fils, jusqu’à
arriver à une feuille, disons f . L’arbre est alors ordonné, mais n’est en général pas
parfait, et la dernière étape est de transférer la clé de la dernière feuille dans f , puis
de la faire remonter à sa place sur la branche entre la racine et f .
Nous renvoyons à la section 4.3.3 pour une analyse fine du coût de construction
d’un tas, et donnons ci-dessous des résultats concernant l’ordre asymptotique du
coût au pire ou en moyenne pour le tri par tas.
Proposition 3.14 Pour les deux mesures de coût Nombre de comparaisons de clés
et Nombre d’échanges de clés :
i) le coût d’un ajout, ou d’une suppression du minimum et réorganisation du tas,
est d’ordre log n au pire, lorsque le tas contient n clés ;
ii) le tri par tas a un coût au pire d’ordre n log n ;
iii) sous le modèle des permutations uniformes pour les tableaux, le tri par tas a un
coût moyen d’ordre n log n.
Preuve
i) Tout d’abord, les algorithmes d’ajout de clés et de suppression du minimum et
reconstruction du tas sont simples à analyser dans le cas le pire : le nombre
18 La suppression dans un tas ne porte jamais sur une clé autre que la clé minimale.
3 Arbres, algorithmes et données
L’insertion d’une nouvelle clé dans un tas peut se faire de deux façons distinctes,
suivant que l’ensemble de toutes les clés est connu ou non. Lorsque le tas est
utilisé pour implémenter une file de priorité, par exemple, les clés arrivent puis sont
supprimées de façon dynamique, et ne sont pas toutes connues avant le début de la
construction du tas ; l’algorithme d’insertion procède en insérant le nouvel élément
comme dernière feuille du tas, puis en le faisant monter à sa place sur le chemin
allant de cette feuille vers la racine. Cet algorithme, dû à Williams, est présenté en
section A.6.3. Par contre, lorsque nous voulons trier un ensemble donné de clés en
utilisant le tri par tas, les clés peuvent être supposées toutes connues à l’avance. Il
existe alors un autre algorithme, dû à Floyd et donné lui aussi en section A.6.3, qui
permet de construire le tas de manière plus efficace que par applications répétées de
l’algorithme de Williams. Son idée de base est de partir de l’arbre parfait marqué
par les n clés, et de le rendre croissant en transformant en tas les « petits » sousarbres au niveau juste au dessus des feuilles, puis ceux dont la racine est au niveau
immédiatement supérieur, et dont les deux sous-arbres sont donc des tas, et ainsi de
suite jusqu’à remonter à la racine de l’arbre.
En ce qui concerne la suppression du minimum du tas, 18 il existe là aussi deux
algorithmes, suivant que l’on rétablit d’abord la structure d’arbre parfait puis celle
d’arbre ordonné, ou l’inverse. Le premier algorithme prend la marque de la dernière
feuille et la met à la racine de l’arbre qui redevient donc un arbre parfait, puis la fait
redescendre vers un niveau plus profond, en reconstruisant la contrainte d’ordre. Le
second algorithme travaille sur un chemin de la racine vers une feuille, en faisant
remonter à chaque niveau, dans le nœud dont la marque a été transférée au niveau
supérieur (ou ôtée dans le cas de la racine) la plus petite marque de ses fils, jusqu’à
arriver à une feuille, disons f . L’arbre est alors ordonné, mais n’est en général pas
parfait, et la dernière étape est de transférer la clé de la dernière feuille dans f , puis
de la faire remonter à sa place sur la branche entre la racine et f .
Nous renvoyons à la section 4.3.3 pour une analyse fine du coût de construction
d’un tas, et donnons ci-dessous des résultats concernant l’ordre asymptotique du
coût au pire ou en moyenne pour le tri par tas.
Proposition 3.14 Pour les deux mesures de coût Nombre de comparaisons de clés
et Nombre d’échanges de clés :
i) le coût d’un ajout, ou d’une suppression du minimum et réorganisation du tas,
est d’ordre log n au pire, lorsque le tas contient n clés ;
ii) le tri par tas a un coût au pire d’ordre n log n ;
iii) sous le modèle des permutations uniformes pour les tableaux, le tri par tas a un
coût moyen d’ordre n log n.
Preuve
i) Tout d’abord, les algorithmes d’ajout de clés et de suppression du minimum et
reconstruction du tas sont simples à analyser dans le cas le pire : le nombre
18 La suppression dans un tas ne porte jamais sur une clé autre que la clé minimale.