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
--
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
