PearlyXD

Drzewa Lewicowe

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