open Okasaki
open OrderedSig
open HeapSig

module LazyPairingHeap (Element : Ordered) : Heap =
struct

   module Element = Element

   type heaps = Empty | Node of Element.t * heaps * heaps Lazy.t
   type heap = heaps

   let empty = Empty

   let is_empty = function
      | Empty -> true
      | _ -> false

   let rec merge a b = 
      match a, b with
      | _, Empty -> a
      | Empty, _ -> b
      | Node (x, _, _), Node (y, _, _) -> 
         if Element.leq x y 
            then link a b 
            else link b a

   and link h a = 
      match h with
      | Node (x, Empty, m) -> Node (x, a, m)
      | Node (x, b, m) -> Node (x, Empty, lazy (merge (merge a b) !$m))
      | _ -> raise BrokenInvariant

   let insert x a = 
      merge (Node (x, Empty, lazy Empty)) a

   let find_min = function 
      | Empty -> raise EmptyStructure
      | Node (x, _, _) -> x

   let delete_min = function 
      | Empty -> raise EmptyStructure
      | Node (_, a, lazy b) -> merge a b

end