Aller au contenu

Tas

On va définir ici des fonctions dans un fichier tas.ml, cela permettra ensuite de l'utiliser dans un autre fichier avec Tas (c'est ce module qui est utilisé dans le TP sur la compression de Huffman). C'est la raison pour laquelle on ne va pas préfixer les noms de fonctions par tas.

On réalise ici des tas max, rangés dans un tableau : la racine est à l'indice 0 et les fils du nœud d'indice \(i\) sont aux indices \(2i+1\) et \(2i+2\).

On propose ici une interface assez simple mais deux améliorations sont proposées librement :

  • faire en sorte de ne pas avoir à donner tout de suite un élément du bon type avant le premier ajout ;
  • faire en sorte de ne pas avoir à donner une capacité initiale en ayant un tas redimensionnable comme les tableaux dynamiques.

On définit le type

type 'a t = {
    elements : 'a array;
    mutable taille : int
}

Question 1. Écrire une fonction

val cree : int -> 'a -> 'a t

telle que cree taille_max defaut crée un tas de capacité maximale taille_max et dont les éléments sont initialisés à defaut.

Corrigé 
let cree taille_max defaut = 
    { 
        elements = Array.make taille_max defaut; 
        taille = 0 
    }

Remarque

C'est une restriction pour le typage d'avoir à passer une valeur par défaut. Vous pouvez vous en passer en changeant le type des éléments du tableau en 'a option et en mettant None partout au début.

Question 2. Écrire des fonctions

val est_vide : 'a t -> bool
val taille : 'a t -> int

qui indiquent respectivement si un tas est vide et son nombre d'éléments.

Corrigé 
let est_vide tas = tas.taille = 0

let taille tas = tas.taille

Question 3. Écrire des fonctions

val pere : int -> int
val gauche : int -> int
val droite : int -> int

qui indiquent les indices respectifs du père, du fils gauche et du fils droit d'un indice donné.

Corrigé 
let pere a =
    if a = 0
    then failwith "racine"
    else (a+1)/2 - 1

let gauche a = 2*(a+1) - 1
let droite a = 2*(a+1)

On a bien \(\text{pere}(i) = \left\lfloor \frac{i-1}{2} \right\rfloor\), \(\text{gauche}(i) = 2i + 1\) et \(\text{droite}(i) = 2i+2\).

Question 4. Écrire une fonction

val maximum : 'a t -> 'a

qui renvoie le maximum d'un tas non vide.

Corrigé

On en profite pour définir deux fonctions utilitaires.

let maximum tas = tas.elements.(0)

let nth tas i = tas.elements.(i)

let swap v x y =
    let t = v.(x) in
    v.(x) <- v.(y);
    v.(y) <- t

Question 5. Écrire une fonction

val ajoute : 'a -> 'a t -> unit

qui rajoute un élément dans le tas.

Corrigé

On place l'élément dans la première case libre puis on le fait remonter tant qu'il est plus grand que son père.

let ajoute x tas =
    let pos = ref tas.taille in
    tas.elements.(tas.taille) <- x;
    tas.taille <- tas.taille + 1;
    while !pos > 0 && nth tas (pere !pos) < nth tas !pos do
        let p = pere !pos in
        swap tas.elements p !pos;
        pos := p
    done

Question 6. Écrire une fonction

val max_pere_fils : 'a t -> int -> int

telle que max_pere_fils tas i renvoie l'indice du plus grand élément entre i, gauche i et droite i (parmi ceux qui sont dans le tas). Ce sera utile pour la fonction suivante.

Corrigé 
let max_pere_fils tas a =
    let max_courant = ref a in

    if tas.taille > gauche a 
        && nth tas (gauche a) > nth tas !max_courant
    then max_courant := gauche a;
    if tas.taille > droite a 
        && nth tas (droite a) > nth tas !max_courant
    then max_courant := droite a;
    !max_courant

Question 7. Écrire une fonction

val extrait_maximum : 'a t -> 'a

qui extrait et renvoie le maximum d'un tas non vide.

Corrigé

On remplace la racine par le dernier élément, puis on le fait descendre en l'échangeant avec le plus grand de ses fils tant que nécessaire.

let extrait_maximum tas =
    assert (tas.taille > 0);
    tas.taille <- tas.taille - 1;
    let x = tas.elements.(0) in
    if tas.taille > 0
    then begin
        let pos = ref 0 in
        tas.elements.(0) <- tas.elements.(tas.taille);
        while max_pere_fils tas !pos <> !pos do
            let max_fils = max_pere_fils tas !pos in
            swap tas.elements !pos max_fils;
            pos := max_fils
        done
    end;
    x

Tri par tas

Question 8. Écrire une fonction

val tri_par_tas : 'a list -> 'a list

qui trie une liste dans l'ordre croissant à l'aide d'un tas.

Corrigé 
let tri_par_tas l =
    match l with
    | [] -> []
    | x :: _ ->
        let tas = cree (List.length l) x in
        List.iter (fun y -> ajoute y tas) l;
        (* on extrait les maxima : on construit la liste
           triée en commençant par la fin *)
        let res = ref [] in
        while not (est_vide tas) do
            res := extrait_maximum tas :: !res
        done;
        !res

Chaque ajout et chaque extraction coûte \(O(\log n)\), le tri coûte donc \(O(n \log n)\).

Comme on l'a vu en classe, on peut réaliser un tri par tas en place dans un tableau.

Question 9. Écrire des fonctions

val vers_tas : 'a array -> unit
val depuis_tas : 'a array -> unit

qui vont respectivement :

  • prendre un tableau et le transformer en place en tableau d'un tas ;
  • prendre un tableau d'un tas et le transformer en place en tableau trié dans l'ordre croissant.
Corrigé 
(* descente de l'élément d'indice i dans le tas formé
   des n premières cases de t *)
let rec descend t n i =
    let m = ref i in
    if gauche i < n && t.(gauche i) > t.(!m) then m := gauche i;
    if droite i < n && t.(droite i) > t.(!m) then m := droite i;
    if !m <> i
    then begin
        swap t i !m;
        descend t n !m
    end

let vers_tas t =
    let n = Array.length t in
    (* les feuilles sont déjà des tas : on traite les nœuds
       internes du dernier vers la racine *)
    for i = n/2 - 1 downto 0 do
        descend t n i
    done

let depuis_tas t =
    let n = Array.length t in
    for k = n-1 downto 1 do
        (* le maximum du tas t.(0..k) va à sa place définitive *)
        swap t 0 k;
        descend t k 0
    done

Pour trier un tableau t en place, il suffit d'appeler vers_tas t puis depuis_tas t.

Files de priorité

On va définir ici un module dans filePriorite.ml qui permettra donc d'accéder à ces fonctions avec FilePriorite.

Comme il faut utiliser Tas, vous pouvez passer par dune pour gérer les modules (voir le TP sur la compression de Huffman) ou compiler à la main.

On considère le type :

type ('a, 'b) t = ('b * 'a) Tas.t

Un élément de type 'a de priorité de type 'b est ainsi stocké dans le tas sous la forme du couple (priorite, element) : comme les couples sont comparés d'abord selon leur première composante, la racine du tas est un élément de priorité maximale.

Question 10. Écrire une fonction

val cree : int -> 'a -> 'b -> ('a, 'b) t

telle que cree taille_max defval defprio crée une file de priorité de taille maximale taille_max et dont les éléments sont initialisés à la valeur defval de priorité defprio.

Remarque

Là aussi, on peut faire mieux avec une fonction cree : unit -> ('a, 'b) t si on le souhaite.

Question 11. Écrire une fonction

val ajoute : ('a, 'b) t -> 'a -> 'b -> unit

qui ajoute un élément avec une priorité donnée.

Question 12. Écrire une fonction

val retire : ('a, 'b) t -> 'a

qui retire un élément quelconque de priorité maximale.

Corrigé des questions 10 à 12 
type ('a, 'b) t = ('b * 'a) Tas.t

let cree taille_max defval defprio = 
    Tas.cree taille_max (defprio, defval)

let ajoute file x p =
    Tas.ajoute (p, x) file

let retire file =
    let _, x = Tas.extrait_maximum file in
    x

On remarque qu'à priorités égales, ce sont les éléments eux-mêmes qui départagent les couples : il faut donc que le type 'a soit comparable avec < (pas de fonctions par exemple).