A Rappels algorithmiques
441
Dans les algorithmes qui suivent, nous supposons que la taille maximale NMAX
de l’arbre est fixée, 5 la taille du tas sera dénoté par un entier n ∈ {0, . . . , NMAX}.
En prenant comme structure de données un tableau de la taille maximale NMAX, un
arbre parfait non vide de taille n se trouve donc dans le sous-tableau T[1 . . n] : le
i-ième nœud a pour marque la clé contenue dans T[i]. Dans la suite, nous parlons
indifféremment d’un arbre parfait de taille n, ou d’un (sous-)tableau T[1 . . n].
Construction du tas : algorithme de Floyd
Si nous connaissons à l’avance toutes les clés à ajouter, nous pouvons construire le
tas à partir de ces clés, avec un algorithme dû à Floyd. Supposons que nous ayons un
algorithme générerTas qui, à partir de deux tas de tailles « compatibles » et d’une
clé, construit un nouveau tas. Alors nous pouvons transformer un arbre parfait en
tas « de bas en haut » (des feuilles vers la racine), par l’algorithme suivant.
Fonction Construire(tableau T, entier n)
// Précondition : T[1 . . n] est un tableau de clés (n ≤ NMAX).
// Postcondition : Retourne le tableau T où les n clés ont été réordonnées en
un tas de taille n, contenu en T[1 . . . n].
// Utilise : générerTas
// Variable locale : entier i
pour i de
n
2
à 1 faire
T = générerTas(T, i)
retourner T
L’algorithme générerTas fusionne en un nouveau tas un parent T[i] et ses deux
tas « fils » T[2i] et T[2i + 1].
5 La valeur NMAX est alors une constante, que nous n’avons pas besoin de passer en paramètre des
algorithmes de manipulation de tas.
441
Dans les algorithmes qui suivent, nous supposons que la taille maximale NMAX
de l’arbre est fixée, 5 la taille du tas sera dénoté par un entier n ∈ {0, . . . , NMAX}.
En prenant comme structure de données un tableau de la taille maximale NMAX, un
arbre parfait non vide de taille n se trouve donc dans le sous-tableau T[1 . . n] : le
i-ième nœud a pour marque la clé contenue dans T[i]. Dans la suite, nous parlons
indifféremment d’un arbre parfait de taille n, ou d’un (sous-)tableau T[1 . . n].
Construction du tas : algorithme de Floyd
Si nous connaissons à l’avance toutes les clés à ajouter, nous pouvons construire le
tas à partir de ces clés, avec un algorithme dû à Floyd. Supposons que nous ayons un
algorithme générerTas qui, à partir de deux tas de tailles « compatibles » et d’une
clé, construit un nouveau tas. Alors nous pouvons transformer un arbre parfait en
tas « de bas en haut » (des feuilles vers la racine), par l’algorithme suivant.
Fonction Construire(tableau T, entier n)
// Précondition : T[1 . . n] est un tableau de clés (n ≤ NMAX).
// Postcondition : Retourne le tableau T où les n clés ont été réordonnées en
un tas de taille n, contenu en T[1 . . . n].
// Utilise : générerTas
// Variable locale : entier i
pour i de
n
2
à 1 faire
T = générerTas(T, i)
retourner T
L’algorithme générerTas fusionne en un nouveau tas un parent T[i] et ses deux
tas « fils » T[2i] et T[2i + 1].
5 La valeur NMAX est alors une constante, que nous n’avons pas besoin de passer en paramètre des
algorithmes de manipulation de tas.