444
A Rappels algorithmiques
Fonction supprimer(tableau T, entier n)
// Précondition : T[1 . . n] est un tas ; 1 ≤ n ≤ NMAX.
// Postcondition : Retourne l’ancien minimum, le tas réorganisé après
suppression du minimum, et sa nouvelle taille.
// Utilise : échanger
// Variables locales : élément min, entier i, entier j, booléen fini
min = T[1]
T[1] = T[n]
n = n - 1
i = 1
fini = (i >
n
2
)
tant que non fini faire
si (n == 2i) ou (T[2i] < T[2i + 1]) alors
j = 2i
sinon
j = 2i + 1
si T[i] > T[j] alors
échanger(T[i],T[j])
i = j
fini = (i >
n
2
)
sinon
fini = Vrai
retourner min, T, n
Mentionnons ici un deuxième algorithme de reconstruction du tas dans lequel,
après en avoir ôté le minimum, nous préservons d’abord la structure d’arbre
croissant en partant de la racine et en faisant remonter le plus petit de ses deux
fils, puis en poursuivant récursivement ce remplacement d’une clé par la plus petite
clé de ses enfants jusqu’à arriver à une feuille. En général, cette feuille (appelonsla f ) n’est pas la dernière de l’arbre, et une deuxième phase est nécessaire, dans
laquelle nous déplaçons la clé X contenue dans la dernière feuille vers la feuille f ,
puis la faisons remonter vers la racine jusqu’à ce qu’elle trouve sa place. Les deux
algorithmes de suppression travaillent en fait sur le même chemin allant de la
racine à une feuille, et aboutissent au même tas résultat lorsque les clés sont toutes
distinctes.
A Rappels algorithmiques
Fonction supprimer(tableau T, entier n)
// Précondition : T[1 . . n] est un tas ; 1 ≤ n ≤ NMAX.
// Postcondition : Retourne l’ancien minimum, le tas réorganisé après
suppression du minimum, et sa nouvelle taille.
// Utilise : échanger
// Variables locales : élément min, entier i, entier j, booléen fini
min = T[1]
T[1] = T[n]
n = n - 1
i = 1
fini = (i >
n
2
)
tant que non fini faire
si (n == 2i) ou (T[2i] < T[2i + 1]) alors
j = 2i
sinon
j = 2i + 1
si T[i] > T[j] alors
échanger(T[i],T[j])
i = j
fini = (i >
n
2
)
sinon
fini = Vrai
retourner min, T, n
Mentionnons ici un deuxième algorithme de reconstruction du tas dans lequel,
après en avoir ôté le minimum, nous préservons d’abord la structure d’arbre
croissant en partant de la racine et en faisant remonter le plus petit de ses deux
fils, puis en poursuivant récursivement ce remplacement d’une clé par la plus petite
clé de ses enfants jusqu’à arriver à une feuille. En général, cette feuille (appelonsla f ) n’est pas la dernière de l’arbre, et une deuxième phase est nécessaire, dans
laquelle nous déplaçons la clé X contenue dans la dernière feuille vers la feuille f ,
puis la faisons remonter vers la racine jusqu’à ce qu’elle trouve sa place. Les deux
algorithmes de suppression travaillent en fait sur le même chemin allant de la
racine à une feuille, et aboutissent au même tas résultat lorsque les clés sont toutes
distinctes.