Drzewa Lewicowe

(*przechowujemy kolejno: lewego syna, prawego syna, wartość (priorytet), npl (null path length)*)
type 'a queue = Node of ('a queue)*('a queue)*('a)*int | Null;;

(*funkcje pomocnicze*)
let npl q =
  match q with
  | Null -> -1
  | Node (Null,_,_,_) -> 0
  | Node (_,Null,_,_) -> 0
  | Node (_,_,_,a) -> a
;;

let empty = Null;;

let rec join queue1 queue2 =
  match (queue1, queue2) with
  | (Null, Null) -> Null
  | (Null,_) -> queue2
  | (_,Null) -> queue1
  | (Node (lewy1,prawy1,wartosc1,npl1), Node (lewy2,prawy2,wartosc2,npl2)) ->
    if (wartosc1<=wartosc2) then
      let d = join prawy1 queue2 in
      if (npl lewy1)<=(npl d) then Node (d,lewy1,wartosc1,(npl lewy1)+1)
      else Node (lewy1,d,wartosc1,(npl d)+1)
    else join queue2 queue1
;;

let add e q = join (Node (Null,Null,e,0)) q;;

let is_empty q =
  match q with
  | Null -> true
  | _ -> false
;;

exception Empty;;
let delete_min q =
  match q with
  | Null -> raise (Empty)
  | Node (lewy,prawy,wartosc,npl) -> (wartosc,(join lewy prawy))
;;