RE: [Caml-list] Priority queues, reloaded

["Jon Harrop" <jon@ffconsultancy.com>]

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.