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