Info_MPSI/MP/JALLAT_tas.ml

let ex1 = [|0;35;21; 27;15;13;14;9;5;2;7;1;6|];;
let ex2 = [|35; 21; 27; 15; 13; 14; 9; 5; 2; 7; 1; 6|];;

let est_tas t = let i = ref 0 and n = Array.length t in
  while (2* !i + 2)<n && t.(!i)>=t.(2 * !i + 1) && t.(!i)<= t.(2 * !i + 2) do
    i:= !i + 1
  done;
  (2* !i + 2) =n && t.(2 * !i +2)<= t.(!i)||(2* !i + 2) =n
;;
est_tas ex1;;
est_tas ex2;;
let rec est_tas_aux t i n = match i with
| i when 2 * i+2>n -> true
| i when 2 * i +2 =n -> t.(2 * i + 2)<= t.(i)
| _ -> t.(i)>=t.(2 * i + 1) && t.(i)<= t.(2 * i + 2) && est_tas_aux t (i+1) n
;;
let est_tas_2 t = est_tas_aux t 0 (Array.length t);;
est_tas_2 ex1;;
est_tas_2 ex2;; 

let est_tas_3 t =
  let n = Array.length t in
    let i = ref (n-1) in
      while !i>0 && t.(!i)>=t.((!i-1)/2) do
        i:= !i - 1
      done;
      !i = 0
;;
est_tas_3 ex1;;
est_tas_3 ex2;;

(*Recursif maintenant*)

let rec est_tas_4_aux t i n = match i with
| i when 2 * i+2>n -> true
| i when 2 * i +2 =n -> t.(2 * i + 2)<= t.(i)
| _ -> t.(i)>=t.(2 * i + 1) && t.(i)<= t.(2 * i + 2) && est_tas_4_aux t (i+1) n
;;
let est_tas_4 t = est_tas_4_aux t 0 (Array.length t);;
est_tas_4 ex1;;
est_tas_4 ex2;;


let swap t i j = let temp = t.(i) in
  t.(i)<-t.(j);
  t.(j)<-temp
;;

let rec insere t k x = match k with
| 0 -> t.(0)<-x
| _ -> if x<t.((k-1)/2) then t.(k)<-x
  else 
    begin
      (t.(k)<-t.((k-1)/2);
      insere t ((k-1)/2) x)
    end;
;;

let rec insere2 t k x = let n = Array.length t in
  match k with
| k when 2 * k+2>n -> t.(k)<-x
| k when 2 * k+2 = n -> if x>=t.(2*k+1) then t.(k)<-x
  else
    begin
      t.(k)<-t.(2*k+1);
      t.(2*k+1)<-x
    end;
| _ -> let m = if t.(2*k+1)>t.(2*k+2) then 2*k+1 else 2*k+2 in
  if x>=t.(m) then t.(k)<-x
  else insere2 t m x
;;

let remontee_sommets t =
  for k = 1 to Array.length t - 1 do
    insere2 t k t.(k)
  done
;;

let descente_peres t =
  let n = Array.length t in
    for k = n/2-1 downto 0 do
      percolation_descendante t n k
    done
;;


type ('a,'b) sommet = {valeur : 'a; mutable priorite : 'b};;

let sommet1_ex = {valeur = 1; priorite = 23};;
sommet1_ex.priorite <- 24;;

type ('a,'b) file_priorite = {mutable taille : int; tab : ('a,'b) sommet array};;

let n = 10;;
let creer_file_vide (v,p) =
  {taille = 0; tab = Array.make n {valeur = v; priorite = p}}
;;

(*Ajout d'un élément dans la file de priorité*)
let ajoute f (v,p) =
  let n = Array.length f.tab in
    if f.taille = n then failwith "File pleine"
    else
      begin
        f.tab.(f.taille)<-{valeur = v; priorite = p};
        f.taille<-f.taille+1;
        remontee_sommets f.tab
      end
;;

(*Suppression du sommet de priorité maximale*)
let supprime_max f =
  if f.taille = 0 then failwith "File vide"
  else
    begin
      let max = f.tab.(0) in
        f.tab.(0)<-f.tab.(f.taille-1);
        f.taille<-f.taille-1;
        descente_peres f.tab;
        max
    end
;;
(*Augmentation de la priorité d'un élément dans la file*)
let augmente_priorite f i p =
  if i<0 || i>=f.taille then failwith "Indice incorrect"
  else
    begin
      f.tab.(i).priorite<-p;
      remontee_sommets f.tab
    end
;;