module heap

type heap<'k, 'v> =
  | E
  | T of 'k * 'v * list<heap<'k, 'v>>

exception EmptyHeap

let empty = E

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

let singleton k v = T (k, v, [])

let merge t1 t2 =
  match t1, t2 with
  | E, h -> h
  | h, E -> h
  | T (kx, vx, xs), T (ky, vy, ys) ->
      if kx <= ky then T (kx, vx, t2::xs) else T (ky, vy, t1::ys)

let insert k v t =
  merge (singleton k v) t

let rec mergePairs = function
  | [] -> E
  | [x] -> x
  | x::y::tl -> merge (merge x y) (mergePairs tl)

let rec findMin = function
  | E -> raise EmptyHeap
  | T (_, v, _) -> v

let rec deleteMin = function
  | E -> raise EmptyHeap
  | T (_, _, xs) -> mergePairs xs