PearlyXD

Untitled

Nov 21st, 2020
698
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. (*przechowujemy kolejno: lewego syna, prawego syna, wartość (priorytet), npl*)
  2. type 'a queue = Node of ('a queue)*('a queue)*('a)*int | Null;;
  3.  
  4. (*funkcje pomocnicze*)
  5. let npl q =
  6.   match q with
  7.   | Null -> -1
  8.   | Node (Null,Null,_,_) -> 0
  9.   | Node (Null,_,_,_) -> 0
  10.   | Node (_,Null,_,_) -> 0
  11.   | Node (_,_,_,a) -> a
  12. ;;
  13.  
  14. let empty = Null;;
  15.  
  16. let rec join queue1 queue2 =
  17.   match (queue1, queue2) with
  18.   | (Null, Null) -> Null
  19.   | (Null,_) -> queue2
  20.   | (_,Null) -> queue1
  21.   | (Node (lewy1,prawy1,wartosc1,npl1), Node (lewy2,prawy2,wartosc2,npl2)) ->
  22.     if (wartosc1<=wartosc2) then
  23.       let d3 = join prawy1 queue2 in
  24.       if (npl lewy1)<=(npl d3) then Node (d3,lewy1,wartosc1,(npl lewy1)+1)
  25.       else Node (lewy1,d3,wartosc1,(npl d3)+1)
  26.     else join queue2 queue1
  27. ;;
  28.  
  29. let add e q = join (Node (Null,Null,e,0)) q;;
  30.  
  31. let is_empty q =
  32.   match q with
  33.   | Null -> true
  34.   | Node(_,_,_,_) -> false
  35. ;;
  36.  
  37. exception Empty;;
  38. let delete_min q =
  39.   if (is_empty q) then raise (Empty)
  40.   else
  41.     match q with
  42.     | Node (lewy,prawy,wartosc,npl) -> (wartosc,(join lewy prawy))
  43. ;;
RAW Paste Data