Meldable Heap (OCaml version)

heap.ml

module type OrderedType = sig
  type t
  val compare : t -> t -> int
end

module type S =
sig
  type elt
  type t
  val empty: t
  val is_empty: t -> bool
  val push: elt -> t -> t
  val top: t -> elt
  val pop: t -> t
end

module Make (Ord : OrderedType) = struct
  type elt = Ord.t
  type t = Node of elt * t * t
         | Leaf

  let rec meld a b =
    match a, b with
    | Leaf, _ -> b
    | _, Leaf -> a
    | Node(av, al, ar), Node(bv, bl, br) ->            
      if Ord.compare av bv > 0 then
        let br = meld br a in
        Node(bv, br, bl)
      else
        let ar = meld ar b in
        Node(av, ar, al)

  let empty = Leaf
  let is_empty = function Leaf -> true | _ -> false 
  let push v h =
    let p = Node(v, Leaf, Leaf) in
    meld h p
  let top h =
    match h with
    | Leaf -> failwith "top"
    | Node(v, _, _) -> v
  let pop h =
    match h with
    | Leaf -> failwith "pop"
    | Node(_, rl, rr) -> meld rr rl
end

heap.mli

module type OrderedType = sig type t val compare : t -> t -> int end
module type S =
  sig
    type elt
    type t
    val empty : t
    val is_empty : t -> bool
    val push : elt -> t -> t
    val top : t -> elt
    val pop : t -> t
  end
module Make (Ord : OrderedType) : S with type elt = Ord.t