A Rappels algorithmiques
443
Fonction ajouter(élément X, tableau T, entier n)
// Précondition : n < NMAX ; T[1 . . n] est un tas.
// Postcondition : Retourne le tableau T représentant le tas obtenu après
ajoute de X dans le tas initial, et la taille de ce tas.
// Utilise : échanger
// Variable locale : entier i
n = n+1
T[n] = X
i = n
tant que (i > 1) et (T[i] < T[
i
2
]) faire
échanger(T[i], T[
i
2
])
i =
i
2
retourner T, n
Bien évidemment, nous pouvons construire un tas en partant d’un arbre initialement vide, et en y ajoutant successivement n clés par l’algorithme d’ajout de
Williams. Cet algorithme de construction d’un tas a un coût en temps en O(n log n)
et se fait sur place (sans mémoire additionnelle).
Suppression du minimum du tas
Le minimum d’un tas se trouve à sa racine ; l’algorithme de suppression du
minimum que nous présentons ici va donc reconstruire d’abord un arbre parfait
en amenant à la racine la clé dans la dernière feuille, puis le réordonner en faisant
descendre cette clé vers le bas de l’arbre (figure A.27).
Fig. A.27 Suppression de la clé à la racine dans un tas : à gauche, l’arbre une fois qu’on a
supprimé la clé à la racine ; à droite, l’arbre parfait – qui n’est plus ordonné – dans lequel la clé 13,
qui était dans la dernière feuille, a été amenée à la racine, et avant de la faire descendre pour qu’elle
trouve sa place dans le sous-arbre adéquat
443
Fonction ajouter(élément X, tableau T, entier n)
// Précondition : n < NMAX ; T[1 . . n] est un tas.
// Postcondition : Retourne le tableau T représentant le tas obtenu après
ajoute de X dans le tas initial, et la taille de ce tas.
// Utilise : échanger
// Variable locale : entier i
n = n+1
T[n] = X
i = n
tant que (i > 1) et (T[i] < T[
i
2
]) faire
échanger(T[i], T[
i
2
])
i =
i
2
retourner T, n
Bien évidemment, nous pouvons construire un tas en partant d’un arbre initialement vide, et en y ajoutant successivement n clés par l’algorithme d’ajout de
Williams. Cet algorithme de construction d’un tas a un coût en temps en O(n log n)
et se fait sur place (sans mémoire additionnelle).
Suppression du minimum du tas
Le minimum d’un tas se trouve à sa racine ; l’algorithme de suppression du
minimum que nous présentons ici va donc reconstruire d’abord un arbre parfait
en amenant à la racine la clé dans la dernière feuille, puis le réordonner en faisant
descendre cette clé vers le bas de l’arbre (figure A.27).
Fig. A.27 Suppression de la clé à la racine dans un tas : à gauche, l’arbre une fois qu’on a
supprimé la clé à la racine ; à droite, l’arbre parfait – qui n’est plus ordonné – dans lequel la clé 13,
qui était dans la dernière feuille, a été amenée à la racine, et avant de la faire descendre pour qu’elle
trouve sa place dans le sous-arbre adéquat