exception Empty

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
  type elt
  type t

  val empty : t
  val is_empty : t -> bool

  val insert : elt -> t -> t
  val merge : t * t -> t

  val find_min : t -> elt
  val delete_min : t -> t
end

module LeftistHeap(Element : ORDERED): Heap =
struct
  type elt = Element.t
  type t = E | T of int * elt * t * t

  let rank = function
  E -> 0
    | T (r, _, _, _) -> r

  let make_t x a b =
    if rank a >= rank b then
      T (rank b + 1, x, a, b)
    else
      T (rank a + 1, x, b, a)

  let empty = E

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

  let rec merge = function
  h, E -> h
    | E, h -> h
    | T (_, x, a1, b1) as h1, (T (_, y, a2, b2) as h2) ->
      if (Element.leq x y) then
        make_t x a1 (merge(b1, h2))
      else
        make_t y a2 (merge(h1, b2))

  let insert x h = merge(T (1, x, E, E), h)

  let find_min = function
  E -> raise Empty
    | T (_, x, a, b) -> x

  let delete_min = function
  E -> raise Empty
    | T (_, x, a, b) -> merge(a, b)
end