From mboxrd@z Thu Jan  1 00:00:00 1970
Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105])
	by walapai.inria.fr (8.13.6/8.13.6) with ESMTP id p5UIEcN4021847
	for <caml-list@sympa-roc.inria.fr>; Thu, 30 Jun 2011 20:14:38 +0200
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: AuQCANm7DE6BryEpkWdsb2JhbABSmGuOcBQBAQEBCQsLBxQEIYh6vzqGMQSXJYs6
X-IronPort-AV: E=Sophos;i="4.65,453,1304287200"; 
   d="scan'208";a="102295335"
Received: from smtp1.u-psud.fr ([129.175.33.41])
  by mail4-smtp-sop.national.inria.fr with ESMTP; 30 Jun 2011 20:14:32 +0200
Received: from smtp1.u-psud.fr (localhost [127.0.0.1])
	by localhost (MTA) with SMTP id C3A6D2508C2
	for <caml-list@inria.fr>; Thu, 30 Jun 2011 20:14:32 +0200 (CEST)
Received: from ext.lri.fr (ext.lri.fr [129.175.15.4])
	by smtp1.u-psud.fr (MTA) with ESMTP id 949E62504F3
	for <caml-list@inria.fr>; Thu, 30 Jun 2011 20:14:32 +0200 (CEST)
Received: from localhost (localhost [127.0.0.1])
	by ext.lri.fr (Postfix) with ESMTP id 9B43F4063A
	for <caml-list@inria.fr>; Thu, 30 Jun 2011 20:14:32 +0200 (CEST)
X-Virus-Scanned: Debian amavisd-new at lri.fr
Received: from ext.lri.fr ([127.0.0.1])
	by localhost (ext.lri.fr [127.0.0.1]) (amavisd-new, port 10024)
	with ESMTP id zAHs+qTMwx00 for <caml-list@inria.fr>;
	Thu, 30 Jun 2011 20:14:32 +0200 (CEST)
Received: from [192.168.0.10] (mry91-1-82-229-156-20.fbx.proxad.net [82.229.156.20])
	(using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits))
	(No client certificate requested)
	by ext.lri.fr (Postfix) with ESMTPSA id 72CF940151
	for <caml-list@inria.fr>; Thu, 30 Jun 2011 20:14:32 +0200 (CEST)
Message-ID: <4E0CBD0A.8090808@lri.fr>
Date: Thu, 30 Jun 2011 20:14:34 +0200
From: =?ISO-8859-1?Q?Jean-Christophe_Filli=E2tre?=
 <Jean-Christophe.Filliatre@lri.fr>
User-Agent: Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:1.9.2.17) Gecko/20110424 Thunderbird/3.1.10
MIME-Version: 1.0
To: caml-list@inria.fr
References: <4E0CAEC3.7010804@gmail.com> <BANLkTinAfZGdJ19mRjpoqVTvN9dpCNymFw@mail.gmail.com>
In-Reply-To: <BANLkTinAfZGdJ19mRjpoqVTvN9dpCNymFw@mail.gmail.com>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 8bit
Subject: Re: [Caml-list] Priority queues, reloaded

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