module type ORDERED =
sig
 type t
 val eq: t -> t -> bool
 val lt: t -> t -> bool
 val leq: t -> t -> bool
end

module type HEAP =
sig
 module Elem: ORDERED
 type heap
 val empty: heap
 val isEmpty: heap -> bool
 val insert: Elem.t -> heap -> heap
 val merge: heap -> heap -> heap
 val findMin: heap -> Elem.t
 val deleteMin: heap -> heap
end

module Bootstrap (MakeH: functor (Element:ORDERED) ->
 HEAP with module Elem = Element)
 (Element: ORDERED) : HEAP with module Elem = Element =
struct
 module Elem = Element
 module rec BE
   : sig type t = E | H of Elem.t * PrimH.heap
         val eq: t -> t -> bool
         val lt: t -> t -> bool
         val leq: t -> t -> bool
   end = struct
     type t = E | H of Elem.t * PrimH.heap
     let leq (H(x, _)) (H(y, _)) = Elem.leq x y
     let eq (H(x, _)) (H(y, _)) = Elem.eq x y
     let lt (H(x, _)) (H(y, _)) = Elem.lt x y
   end
 and PrimH
   : HEAP with type Elem.t = BE.t
   = MakeH(BE)
 type heap = BE.t
 let empty = BE.E
 let isEmpty = function BE.E -> true | _ -> false
 let rec merge x y =
   match (x,y) with
       (BE.E, _) -> y
     | (_, BE.E) -> x
     | (BE.H(e1,p1) as h1), (BE.H(e2,p2) as h2) ->
         if Elem.leq e1 e2
         then BE.H(e1, PrimH.insert h2 p1)
         else BE.H(e2, PrimH.insert h1 p2)
 let insert x h =
   merge (BE.H(x, PrimH.empty)) h
 let findMin = function
     BE.E -> raise Not_found
   | BE.H(x, _) -> x
 let deleteMin = function
     BE.E -> raise Not_found
   | BE.H(x, p) ->
       if PrimH.isEmpty p then BE.E else begin
         let (BE.H(y, p1)) = PrimH.findMin p in
         let p2 = PrimH.deleteMin p in
         BE.H(y, PrimH.merge p1 p2)
       end
end