I. Implémentation d'un tas min

Les tas sont un type d'arbre binaire avec quelques propriétés supplémentaires.

On définit un tas min comme :

• Soit une feuille
• Soit un noeud, qui a une étiquette et deux fils (droite et gauche)

De plus,

1. si un noeud est étiquetté par et y l'étiquette d'un de ses fils, on a . Ainsi, les fils sont toujours plus grands que leur pères.
2. le tas doit être semi-complet, c'est à dire que tous les niveaux sauf le dernier doivent être remplis.

En dessous de l'arbre, les mêmes éléments rangés "dans l'ordre de lecture" (niveau par niveau, de gauche à droite) : cela servira dans la partie II. Survolez une case pour la retrouver dans l'arbre.

On donne le type OCaml suivant pour un tas min :

type tas = F | N of int * tas * int * tas;;

A chaque noeud N, on associe

• la hauteur du sous arbre enraciné en N
• le fils gauche de N
• l'étiquette de N
• le fils droite de N

On vous donne également une variable tas_test contenant le tas ci-dessus, et une fonction affiche_tas qui permet d'afficher un tas.

let tas_test = N (3, 
                    N (2, 
                        N (1, 
                            N (0, F, 25, F),
                            17,
                            N (0, F, 100, F)),
                        2, 
                        N (0, F, 19, F)),
                    1, 
                    N (1, 
                        N (0, F, 36, F),
                        3,
                        N (0, F, 7, F))
                );;
                

let affiche_tas t = 
    let rec aux t indentl indentr = match t with 
    |F -> ()
    |N(_, t2, x, t1) -> aux t1 (indentl^"\t ") (indentl^"\t|") ; 
    Printf.printf "%s%d ----%s|\n" indentl x (if x > 10 then "" else "-"); 
    aux t2 (indentr^"\t|") (indentr^"\t "); 
    print_string indentr; 
    print_newline ()
    in 
    aux t " " ""
;;

affiche_tas tas_test;;

let decoupe t = match t with
    | F -> None
    | N (_, g, x, d) -> Some (g, string_of_int x, d);;

afficher_arbre_binaire decoupe tas_test;;

On aimerait maintenant définir deux opérations sur les tas :

• l'ajout d'un élément
• l'extraction de l'élément minimal

Dans les deux cas, on va en fait ajouter / retirer les éléments uniquement à la fin du tas, c'est à dire l'élément le plus a droite du dernier niveau.

Maintenant, on a un tas dont la racine ne respecte plus forcément la propriété 1. (voir schéma ci-dessus).

let descend (t: tas): tas = failwith "à compléter"

let extrait_min (t: tas): int * tas = failwith "à compléter"

let ajout (t: tas) (el: int): tas = failwith "à compléter"

Complexité des opérations

On va s'intérésser à la complexité des opérations en fonction du nombre total d'éléments dans le tas.

Tri par tas

Le tri par tas est un algorithme de tri simple (une fois qu'on a implémenté un tas) : on ajoute tous les éléments de notre liste au tas, puis on extrait le minimum jusqu'à ce que celui-ci soit vide.

II. Implémentation d'un tas avec un tableau

Plutot que d'utiliser une structure récursive immutable, on propose d'utiliser un tableau pour stocker notre tas. On utilise la représentation suivante :

• la racine est stockée à l'indice 0
• si un élément est stocké à l'indice i, son fils gauche est à la position 2i + 1 et son fils droite 2i + 2
• les éléments absents sont représentés par "-1".

À noter que cela revient à placer les éléments dans l'ordre "de lecture".

On défini le type OCaml suivant, ainsi qu'à nouveau une fonction d'affichage et un tas de test.

type tas_bleau = int array;;

let tas_bleau_test = [|1; 2; 3; 17; 19; 36; 7; 25; 100; -1; -1; -1; -1; -1; -1|];;

La fonction afficher_tas du site dessine un tas stocké dans un tableau, sous forme d'arbre et de tableau. L'argument optionnel ~taille indique le nombre de cases utilisées :

afficher_tas ~taille:9 tas_bleau_test;;

Vous pouvez aussi manipuler le tas ci-dessous : ajoutez des éléments et extrayez le minimum, en observant ce qui se passe dans le tableau.

Pour, par exemple, l'algorithme de Dijkstra, il manque une opération à implémenter (qui est plus simple à implémenter sur le tableau) : la mise à jour d'un noeud.

L'idée est de, si on augmente un noeud, on va le déplacer vers le bas, et sinon, on va le déplacer vers le haut.

III. File de priorité

Pour l'algorithme de Dijkstra, on a besoin d'une file de priorité : une structure qui stocke des éléments associés à des priorités (des entiers), avec les opérations ajouter et extraire_min (qui renvoie l'élément de plus petite priorité). On l'implémente avec un tas min stocké dans un tableau, comme dans la partie II, mais qui contient des couples (priorité, élément), et on garde en mémoire le nombre de cases utilisées.

type 'a file_priorite = {
  mutable taille : int;
  donnees : (int * 'a) array   (* couples (priorité, élément) *)
};;

let f = creer 10 "";;
List.iter (fun (x, p) -> ajouter f x p) [("réviser", 3); ("manger", 1); ("dormir", 2); ("jouer", 5)];;
while not (est_vide f) do
  let (p, x) = extraire_min f in
  Printf.printf "%s (priorité %d)\n" x p
done;;

Entrez le code donné en cours pour accéder à la solution :