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 p5UIaJRW022437 for ; Thu, 30 Jun 2011 20:36:19 +0200 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AuQCAHLBDE6BryEpkWdsb2JhbABSmGuObxQBAQEBCQsLBxQEIYh6vxqGMQSXJYs6 X-IronPort-AV: E=Sophos;i="4.65,453,1304287200"; d="scan'208";a="102296052" Received: from smtp1.u-psud.fr ([129.175.33.41]) by mail4-smtp-sop.national.inria.fr with ESMTP; 30 Jun 2011 20:36:13 +0200 Received: from smtp1.u-psud.fr (localhost [127.0.0.1]) by localhost (MTA) with SMTP id 7BB682562B2 for ; Thu, 30 Jun 2011 20:36:13 +0200 (CEST) Received: from ext.lri.fr (ext.lri.fr [129.175.15.4]) by smtp1.u-psud.fr (MTA) with ESMTP id 668982562B1 for ; Thu, 30 Jun 2011 20:36:13 +0200 (CEST) Received: from localhost (localhost [127.0.0.1]) by ext.lri.fr (Postfix) with ESMTP id 6376C4063C for ; Thu, 30 Jun 2011 20:36:13 +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 I3zFnCGYoXTY for ; Thu, 30 Jun 2011 20:36:13 +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 1C15440343 for ; Thu, 30 Jun 2011 20:36:13 +0200 (CEST) Message-ID: <4E0CC220.8010706@lri.fr> Date: Thu, 30 Jun 2011 20:36:16 +0200 From: =?ISO-8859-1?Q?Jean-Christophe_Filli=E2tre?= 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> In-Reply-To: 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 : > implementation -- or more exotic heaps. I was once in a situation > similar to yours and found that I could implement both his leftist heap > and the red-black trees in around 15 minutes. Wow, that's impressive! But I guess you didn't need to implement the remove operation on red-black trees :-) That's a real pain. Frankly, AVLs are not *that* difficult to implement. And contrary to what you can read in some books, it is really difficult to get anything faster. -- Jean-Christophe