(***** Q1 *****)

(* un tache est juste representee par sa date d'exécution) *)

(* recupere la premiere tache *)
let first = hd;;

(* enleve la premiere tache *)
let pop = tl;;

(* insere une nouvelle tache *)
let rec insert d = function
| [] -> [d]
| t::q ->  if d<t then d::(t::q)
  else t::(insert d q);;

(***** Q2 *****)

let fg i = 2*i + 1;;

let fd i = 2*i + 2;;

let pere i = (i-1)/2;;
 
(***** Q Int *****)

let swap_vect v i j = let tmp = v.(i) in v.(i)<-v.(j); v.(j)<-tmp;;

(***** Q3 *****)

type tas == int ref * (int vect);; 

let cree_tas  n = (ref 0,make_vect n 0);;

let verif (n,d) =  let ok = ref true in
 for i=1 to !n-1 do  if d.(pere i)>d.(i) then ok:=false done;
!ok;;

verif (ref 5,[|1;2;4;3;4;99;99;99|]);;
verif (ref 4,[|1;3;2;2;-1|]);;

(***** Q4 *****)

let rec corrige_up (n,d) i =
 if i>0 && d.(i) < d.(pere i) then (
  swap_vect d i (pere i);
  corrige_up (n,d) (pere i)
);;
 
let inser (n,d) date =
  d.(!n)<-date;
  incr n;
  corrige_up (n,d) (!n-1);;

let inser2 (n,d) date =
  d.(!n)<-date;
  let i = ref !n in
  while !i>0 && d.(pere !i) > d.(!i) do
    swap_vect d !i (pere !i);
    i:=pere !i;
  done;
  incr n;;

let rand_tas n = let t = cree_tas n in
 for i=0 to n-1 do inser t (random__int n) done;
t;;

verif (rand_tas 20);;

(***** Q5 *****)

let rec corrige_down (n,d) i =
  let f = if fd i >= !n || d.(fg i)<d.(fd i) then fg i else fd i in
    if f < !n && d.(f) < d.(i) then (
     swap_vect d i f;
     corrige_down (n,d) f;
    );;
 
let pop (n,d) = let d0 = d.(0) in
 decr n;
 d.(0) <- d.(!n);
 corrige_down (n,d) 0;
 d0;;

let pop2 (n,d) = let d0 = d.(0) in
 decr n;
 d.(0) <- d.(!n);
 let i = ref 0 and ok=ref false in
 while not !ok do
  let f = if fd !i >= !n || d.(fg !i)<d.(fd !i) then fg !i else fd !i in
    if f < !n && d.(f) < d.(!i) then swap_vect d !i f else ok:=true;
    i:=f;
 done;
 d0;;

let t = rand_tas 10000 in for x=1 to 9000 do let yo = pop t in () done;
verif t;;