Re: [Caml-list] Priority queues, reloaded

["Jean-Christophe Filliâtre" <Jean-Christophe.Filliatre@lri.fr>]

Le 30/06/2011 19:26, Gabriel Scherer a écrit :
> Okasaki (eg. in its book "Purely functional data structure", but can
> probably be found in papers available on the net) has a "leftist heap"
> data structure that is also compact and, to my personal taste, easier to
> understand, get familiar with and remember than the usual heap
> implementation -- or more exotic heaps.

I confirm that leftist heap is probably the best possible choice. Here 
is the code (and if you don't need a functor, it is even shorter):


module Make(X : sig type t val le : t -> t -> bool end) :
sig
   type t
   val empty : t
   val is_empty : t -> bool
   val add : X.t -> t -> t
   exception Empty
   val min : t -> X.t
   val extract_min : t -> X.t * t
   val merge : t -> t -> t
end
=
struct

   type t = E | T of int * X.t * t * t

   exception Empty

   let rank = function E -> 0 | T (r,_,_,_) -> r

   let make x a b =
     let ra = rank a and rb = rank b in
     if ra >= rb then T (rb + 1, x, a, b) else T (ra + 1, x, b, a)

   let empty = E

   let is_empty = function E -> true | T _ -> false

   let rec merge h1 h2 = match h1,h2 with
     | E, h | h, E ->
	h
     | T (_,x,a1,b1), T (_,y,a2,b2) ->
	if X.le x y then make x a1 (merge b1 h2) else make y a2 (merge h1 b2)

   let add x h = merge (T (1, x, E, E)) h

   let min = function E -> raise Empty | T (_,x,_,_) -> x

   let extract_min = function
     | E -> raise Empty
     | T (_,x,a,b) -> x, merge a b

end

-- 
Jean-Christophe