From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82]) by walapai.inria.fr (8.13.6/8.13.6) with ESMTP id p5UMHG9H028849 for ; Fri, 1 Jul 2011 00:17:16 +0200 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AvsBAGv0DE5KfVK2kGdsb2JhbAAxCxaEQpN3jxwIFAEBAQEJCQ0HFAQhiHgColCLYoMJAY1GBYErg3qBDJIziUWCVzyDVw X-IronPort-AV: E=Sophos;i="4.65,454,1304287200"; d="scan'208";a="112287870" Received: from mail-wy0-f182.google.com ([74.125.82.182]) by mail1-smtp-roc.national.inria.fr with ESMTP/TLS/RC4-SHA; 01 Jul 2011 00:17:10 +0200 Received: by wyg24 with SMTP id 24so3337553wyg.27 for ; Thu, 30 Jun 2011 15:17:10 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlemail.com; s=gamma; h=from:to:cc:subject:references:date:in-reply-to:message-id :user-agent:mime-version:content-type:content-transfer-encoding; bh=0RfnC43nj8sit0xIFQJRlOTVjrl2aZArdp2JwgNKcgU=; b=yEa4pEYiIxtCAJxh6fgBOAJlR86pbpf1z0Xz5B29/NhsBFx4463hO7H1NIcS2JqX8n Ul0K13g7YfeC4WSN50v061vR56we77LbA97Jtw0KKab0K6kBTaiFgERGFhKl2paKEyrZ HpcI2OOzSJBu9SQPjtPIPZlEzYqtIDRjmiaUo= Received: by 10.216.35.76 with SMTP id t54mr515444wea.26.1309472230245; Thu, 30 Jun 2011 15:17:10 -0700 (PDT) Received: from spec-desktop.danmey.org (cpc1-cmbg12-0-0-cust201.5-4.cable.virginmedia.com [86.9.116.202]) by mx.google.com with ESMTPS id n18sm1925802wbh.57.2011.06.30.15.17.08 (version=TLSv1/SSLv3 cipher=OTHER); Thu, 30 Jun 2011 15:17:09 -0700 (PDT) From: Wojciech Meyer To: Gabriel Scherer Cc: Andrew , caml-list@inria.fr References: <4E0CAEC3.7010804@gmail.com> Date: Thu, 30 Jun 2011 23:17:07 +0100 In-Reply-To: (Gabriel Scherer's message of "Thu, 30 Jun 2011 19:26:32 +0200") Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.0.50 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by walapai.inria.fr id p5UMHG9H028849 X-Validation-by: wojciech.meyer@googlemail.com Subject: Re: [Caml-list] Priority queues, reloaded Gabriel Scherer writes: > The heap implementation in the OCaml manual, which was pointed to in > the precedent thread, is quite compact. > > 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 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. Yes, they are nice, and I'd also recommend reading whole book if you have some time for a good lecture. The examples are in Standard ML so it's nearly direct translation to OCaml. I think it was mentioned but Markus Mottl has implemented Okasaki's data structures in OCaml and made it available on his website. One thing to note is that you don't need really laziness in case of leftitst heaps and red-black trees, as far as I recall both are amortised. Cheers; Wojciech > > On Thu, Jun 30, 2011 at 7:13 PM, Andrew > wrote: > > Hi all, > > 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. > > Thanks! > > -- > 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 > >