Construction d'un tas binaire

On choisit de construire un tas max implémenté par un type array OCaml. L'objectif de cet exercice est d'explorer deux méthodes différentes pour construire ce tas max à partir d'un tableau non trié :

• l'approche par montées successives (up)
• et l'approche optimale par descentes successives (down).

1. 1

   Indice

   Utiliser une variable temporaire pour conserver la valeur d'un élément avant de faire l'échange.

   Échanger : Écrire une fonction echanger : 'a array -> int -> int -> unit qui échange en place les éléments des indices i et j du tableau t. Exemple : let a = [|1;2;3|] in echanger a 0 2; a modifie le tableau en [|3; 2; 1|].

2. 2

   Indice

   Calculer l'indice du parent avec $(i-1)/2$ et comparer avant d'échanger.

   Faire monter : Écrire une fonction monter : 'a array -> int -> unit qui fait remonter l'élément situé à l'indice i jusqu'à ce que la propriété du tas maximum soit restaurée. Par exemple : let a = [|10; 5; 8; 15|] in monter a 3; a modifie le tableau en [|15; 10; 8; 5|].

3. 3

   Indice

   Boucler de l'indice 1 à n-1 en appliquant la fonction monter de la gauche vers la droite.

   Construire par montée : Écrire une fonction construire_tas_par_montee : 'a array -> unit qui transforme un tableau en tas max en faisant monter successivement chaque élément, en parcourant le tableau de l'indice 1 jusqu'à la fin. Par exemple : let a = [|1; 2; 3; 4; 5|] in construire_tas_par_montee a; a modifie le tableau en [|5; 4; 2; 1; 3|].

4. 4

   Indice

   Identifier le plus grand élément parmi le nœud et ses enfants puis échanger récursivement si nécessaire.

   Faire descendre : Écrire une fonction descendre : 'a array -> int -> int -> unit qui tamise en place le sous-arbre d'indice i pour respecter la propriété d'un tas maximum. Le deuxième paramètre représente la taille du tas. Par exemple : let a = [|1; 5; 3|] in descendre a 3 0; a modifie le tableau en [|5; 1; 3|].

5. 5

   Indice

   Parcourir les nœuds internes de bas en haut afin d'appliquer systématiquement l'opération de tamisage.

   Construire par descente : Écrire une fonction construire_tas_par_descente : 'a array -> unit qui transforme en place un tableau arbitraire en un tas maximum valide. Pour cela, appelez descendre sur tous les nœuds internes du tableau, en allant de l'indice n / 2 - 1 jusqu'à la racine (0). Par exemple : let a = [|1; 2; 3; 4; 5|] in construire_tas_par_descente a; a modifie le tableau en [|5; 4; 3; 1; 2|].