442
A Rappels algorithmiques
Fonction génèrerTas(tableau T, entier n, entier i)
// Précondition : NMAX ≥ n ≥ 2i ; T est un tableau représentant un arbre
parfait ; le sous-arbre de racine T[2i], et celui de racine T[2i+1] si
NMAX ≥ n ≥ 2i + 1, sont des tas.
// Postcondition : Retourne le tableau T représentant un arbre parfait où le
sous-arbre de racine T[i] a été restructuré en un tas ; les autres sous-arbres
sont inchangés.
// Utilise : échanger, générerTas
// Variable locale : entier imax
si (n == 2i) et (T[i] > T[2i]) alors
// cas particulier où le nœud n’a qu’un fils
échanger(T[i], T[2i])
sinon
si T[2i] ≤ T[2i+1] alors
imax = 2i
sinon
imax = 2i + 1
si T[imax] < T[i] alors
échanger(T[imax], T[i])
T = générerTas(T, imax, n)
retourner T
L’algorithme de construction du tas pour un tableau de taille n a une complexité
en temps O(n) et se fait sur place (sans mémoire additionnelle).
Ajout d’une clé : algorithme de Williams
Cet algorithme permet d’insérer de manière dynamique une clé dans un tas qui
n’est pas plein (c’est la précondition n < NMAX ci-dessous). Pour cela, une feuille
est d’abord ajoutée au tas, dans laquelle est stockée la nouvelle clé : la structure
d’arbre parfait est donc préservée, et il reste à rétablir l’ordre en faisant remonter la
clé sur le chemin de la dernière feuille à la racine, jusqu’à ce qu’elle trouve sa place
(figure A.26).
Fig. A.26 Ajout de la clé 2
dans un tas de taille 13 : la clé
va être échangée avec 7, puis
avec 4, pour trouver sa place
en enfant droit de la racine
A Rappels algorithmiques
Fonction génèrerTas(tableau T, entier n, entier i)
// Précondition : NMAX ≥ n ≥ 2i ; T est un tableau représentant un arbre
parfait ; le sous-arbre de racine T[2i], et celui de racine T[2i+1] si
NMAX ≥ n ≥ 2i + 1, sont des tas.
// Postcondition : Retourne le tableau T représentant un arbre parfait où le
sous-arbre de racine T[i] a été restructuré en un tas ; les autres sous-arbres
sont inchangés.
// Utilise : échanger, générerTas
// Variable locale : entier imax
si (n == 2i) et (T[i] > T[2i]) alors
// cas particulier où le nœud n’a qu’un fils
échanger(T[i], T[2i])
sinon
si T[2i] ≤ T[2i+1] alors
imax = 2i
sinon
imax = 2i + 1
si T[imax] < T[i] alors
échanger(T[imax], T[i])
T = générerTas(T, imax, n)
retourner T
L’algorithme de construction du tas pour un tableau de taille n a une complexité
en temps O(n) et se fait sur place (sans mémoire additionnelle).
Ajout d’une clé : algorithme de Williams
Cet algorithme permet d’insérer de manière dynamique une clé dans un tas qui
n’est pas plein (c’est la précondition n < NMAX ci-dessous). Pour cela, une feuille
est d’abord ajoutée au tas, dans laquelle est stockée la nouvelle clé : la structure
d’arbre parfait est donc préservée, et il reste à rétablir l’ordre en faisant remonter la
clé sur le chemin de la dernière feuille à la racine, jusqu’à ce qu’elle trouve sa place
(figure A.26).
Fig. A.26 Ajout de la clé 2
dans un tas de taille 13 : la clé
va être échangée avec 7, puis
avec 4, pour trouver sa place
en enfant droit de la racine