exception Empty
module type ORDERED = sig
type t
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+IChFLCBFKQogIAogICAgbGV0IGluc2VydCB4IHQgPSBsZXQgYSwgYiA9IHBhcnRpdGlvbiB4IHQgaW4gVCAoYSx4LGIpCiAgICAKICAgIGxldCByZWMgbWVyZ2UgeiA9IG1hdGNoIHogd2l0aAogICAgICAgICAgfCBFIHQgICAgICAgICAtPiB0CiAgICAgICAgICB8IChUIChhLHgsYikpIHQgLT4gbGV0IHRhLHRiID0gcGFydGl0aW9uIHggdCBpbiBUICgobWVyZ2UgdGEgYSksIHgsIChtZXJnZSB0YiBiKSkgICAKICAgIAogICAgbGV0IHJlYyBmaW5kX21pbiB6ID0gbWF0Y2ggeiB3aXRoCiAgICAgICAgfCBFICAgICAgICAgICAtPiBmYWlsd2l0aCAiZW1wdHkgaGVhcCIKICAgICAgICB8IChUIChFLHgsYikpIC0+IHgKICAgICAgICB8IChUIChhLHgsYikpIC0+IGZpbmRfbWluIGEKCiAgICBsZXQgcmVjIGRlbGV0ZU1pbiB6ID0gbWF0Y2ggeiB3aXRoCiAgICAgICAgfCBFICAgICAgICAgICAgICAgICAtPiBmYWlsd2l0aCAiZW1wdHkgaGVhcCIKICAgICAgICB8IChUIEUgeCBiKSAgICAgICAgIC0+IGIKICAgICAgICB8IChUIChUIEUgeCBiKSB5IGMpIC0+IFQgYiB5IGMKICAgICAgICB8IChUIChUIGEgeCBiKSB5IGMpIC0+IFQgKGRlbGV0ZU1pbiBhKSB4IChUIGIgeSBjKQplbmQK