Andrew wrote:
> Since the previous discussion regarding priority queues pretty much
concluded
> that they weren't available in OCaml, could you point to the most compact
> implementation that you know of? I'm very likely to have to recode my own
> implementation in a time-restricted setting, so I'd love to hear about
efficient-
> yet-easy/fast-to-implement options.
Skew heap from Okasaki translated to OCaml:
module SkewHeap(Elt: Set.OrderedType) = struct
type t = E | T of Elt.t * t * t
let empty = E
let is_empty = function E -> true | _ -> false
let rec merge t1 t2 =
match t1, t2 with
| E, t | t, E -> t
| T(x, l1, r1), T(y, l2, r2) ->
let c = Elt.compare x y in
if c<=0 then T(x, merge t2 r1, l1) else T(y, merge t1 r2, l2)
let insert x h = merge (T(x, E, E)) h
let min = function
| E -> None
| T(x, l, r) -> Some(x, merge l r)
end;;
Cheers,
Jon.
--
Caml-list mailing list. Subscription management and archives:
https://sympa-roc.inria.fr/wws/info/caml-list
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
Bug reports: http://caml.inria.fr/bin/caml-bugs
