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
    module Elem : ORDERED
 
    type heap
 
    val empty : heap
    val is_empty : heap -> bool
 
    val insert : Elem.t -> heap -> heap
    val merge : heap -> heap -> heap
 
    val find_min : heap -> Elem.t
    val delete_min : heap -> heap
end
 
module SplayHeap (Element : ORDERED) : (HEAP with module Elem = Element) =
struct
  module Elem = Element
 
  type heap = E | T of heap * Elem.t * heap
 
  let empty = E
  let is_empty = ( = ) E
 
  let rec partition pivot = function
    | T (a, x, b) as t -> 
      if x <= pivot then begin
          match b with
            | E -> (t, E)
            | T (b', y, b'') ->
                if y <= pivot then
                    let (small, big) = partition pivot b''
                    in (T (T (a, x, b), y, small), big)
                else
                    let (small,big) = partition pivot b'
                    in (T (a, x, small), T (big, y, b''))
        end else begin
          match a with
            | E -> (E, t)
            | T (a', y, a'') ->
                if y <= pivot then
                    let (small, big) = partition pivot a''
                    in (T (a', y, small), T (big, x, b))
                else
                    let (small, big) = partition pivot a'
                    in (small, T (big, y, T (a'', x, b)))
        end
    | E -> (E, E)
 
    let insert x t = let a, b = partition x t in T (a,x,b)
 
    let rec merge z = match z with
          | E t         -> t
          | (T a x b) t -> let ta,tb = partition x t in T (merge ta a) x (merge tb b)
 
    let rec find_min z = match z with
        | E           -> failwith "empty heap"
        | (T (E,x,b)) -> x
        | (T (a,x,b)) -> find_min a
 
    let rec deleteMin z = match z with
        | E                 -> failwith "empty heap"
        | (T E x b)         -> b
        | (T (T E x b) y c) -> T b y c
        | (T (T a x b) y c) -> T (deleteMin a) x (T b y c)
end
 

ZXhjZXB0aW9uIEVtcHR5Cgptb2R1bGUgdHlwZSBPUkRFUkVEID0gc2lnCiAgICB0eXBlIHQKCiAgICB2YWwgZXEgOiB0IC0+IHQgLT4gYm9vbAogICAgdmFsIGx0IDogdCAtPiB0IC0+IGJvb2wKICAgIHZhbCBsZXEgOiB0IC0+IHQgLT4gYm9vbAplbmQKCm1vZHVsZSB0eXBlIEhFQVAgPSBzaWcKICAgIG1vZHVsZSBFbGVtIDogT1JERVJFRAoKICAgIHR5cGUgaGVhcAoKICAgIHZhbCBlbXB0eSA6IGhlYXAKICAgIHZhbCBpc19lbXB0eSA6IGhlYXAgLT4gYm9vbAoKICAgIHZhbCBpbnNlcnQgOiBFbGVtLnQgLT4gaGVhcCAtPiBoZWFwCiAgICB2YWwgbWVyZ2UgOiBoZWFwIC0+IGhlYXAgLT4gaGVhcAoKICAgIHZhbCBmaW5kX21pbiA6IGhlYXAgLT4gRWxlbS50CiAgICB2YWwgZGVsZXRlX21pbiA6IGhlYXAgLT4gaGVhcAplbmQKCm1vZHVsZSBTcGxheUhlYXAgKEVsZW1lbnQgOiBPUkRFUkVEKSA6IChIRUFQIHdpdGggbW9kdWxlIEVsZW0gPSBFbGVtZW50KSA9CnN0cnVjdAogIG1vZHVsZSBFbGVtID0gRWxlbWVudAoKICB0eXBlIGhlYXAgPSBFIHwgVCBvZiBoZWFwICogRWxlbS50ICogaGVhcAoKICBsZXQgZW1wdHkgPSBFCiAgbGV0IGlzX2VtcHR5ID0gKCA9ICkgRQoKICBsZXQgcmVjIHBhcnRpdGlvbiBwaXZvdCA9IGZ1bmN0aW9uCiAgICB8IFQgKGEsIHgsIGIpIGFzIHQgLT4gCiAgICAgIGlmIHggPD0gcGl2b3QgdGhlbiBiZWdpbgogICAgICAgICAgbWF0Y2ggYiB3aXRoCiAgICAgICAgICAgIHwgRSAtPiAodCwgRSkKICAgICAgICAgICAgfCBUIChiJywgeSwgYicnKSAtPgogICAgICAgICAgICAgICAgaWYgeSA8PSBwaXZvdCB0aGVuCiAgICAgICAgICAgICAgICAgICAgbGV0IChzbWFsbCwgYmlnKSA9IHBhcnRpdGlvbiBwaXZvdCBiJycKICAgICAgICAgICAgICAgICAgICBpbiAoVCAoVCAoYSwgeCwgYiksIHksIHNtYWxsKSwgYmlnKQogICAgICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgICAgIGxldCAoc21hbGwsYmlnKSA9IHBhcnRpdGlvbiBwaXZvdCBiJwogICAgICAgICAgICAgICAgICAgIGluIChUIChhLCB4LCBzbWFsbCksIFQgKGJpZywgeSwgYicnKSkKICAgICAgICBlbmQgZWxzZSBiZWdpbgogICAgICAgICAgbWF0Y2ggYSB3aXRoCiAgICAgICAgICAgIHwgRSAtPiAoRSwgdCkKICAgICAgICAgICAgfCBUIChhJywgeSwgYScnKSAtPgogICAgICAgICAgICAgICAgaWYgeSA8PSBwaXZvdCB0aGVuCiAgICAgICAgICAgICAgICAgICAgbGV0IChzbWFsbCwgYmlnKSA9IHBhcnRpdGlvbiBwaXZvdCBhJycKICAgICAgICAgICAgICAgICAgICBpbiAoVCAoYScsIHksIHNtYWxsKSwgVCAoYmlnLCB4LCBiKSkKICAgICAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgICAgICAgICBsZXQgKHNtYWxsLCBiaWcpID0gcGFydGl0aW9uIHBpdm90IGEnCiAgICAgICAgICAgICAgICAgICAgaW4gKHNtYWxsLCBUIChiaWcsIHksIFQgKGEnJywgeCwgYikpKQogICAgICAgIGVuZAogICAgfCBFIC0+IChFLCBFKQogIAogICAgbGV0IGluc2VydCB4IHQgPSBsZXQgYSwgYiA9IHBhcnRpdGlvbiB4IHQgaW4gVCAoYSx4LGIpCiAgICAKICAgIGxldCByZWMgbWVyZ2UgeiA9IG1hdGNoIHogd2l0aAogICAgICAgICAgfCBFIHQgICAgICAgICAtPiB0CiAgICAgICAgICB8IChUIGEgeCBiKSB0IC0+IGxldCB0YSx0YiA9IHBhcnRpdGlvbiB4IHQgaW4gVCAobWVyZ2UgdGEgYSkgeCAobWVyZ2UgdGIgYikKCiAgICBsZXQgcmVjIGZpbmRfbWluIHogPSBtYXRjaCB6IHdpdGgKICAgICAgICB8IEUgICAgICAgICAgIC0+IGZhaWx3aXRoICJlbXB0eSBoZWFwIgogICAgICAgIHwgKFQgKEUseCxiKSkgLT4geAogICAgICAgIHwgKFQgKGEseCxiKSkgLT4gZmluZF9taW4gYQoKICAgIGxldCByZWMgZGVsZXRlTWluIHogPSBtYXRjaCB6IHdpdGgKICAgICAgICB8IEUgICAgICAgICAgICAgICAgIC0+IGZhaWx3aXRoICJlbXB0eSBoZWFwIgogICAgICAgIHwgKFQgRSB4IGIpICAgICAgICAgLT4gYgogICAgICAgIHwgKFQgKFQgRSB4IGIpIHkgYykgLT4gVCBiIHkgYwogICAgICAgIHwgKFQgKFQgYSB4IGIpIHkgYykgLT4gVCAoZGVsZXRlTWluIGEpIHggKFQgYiB5IGMpCmVuZAo=