From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by walapai.inria.fr (8.13.6/8.13.6) with ESMTP id p5UHQuca019910 for ; Thu, 30 Jun 2011 19:26:56 +0200 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: ApIBAMuwDE7RVdy2mGdsb2JhbAA8AQMSmDM0hloBhyljCBQBAQEBAQgJDQcUJYh4onCMIIJLhDw5iGgCAwaGKwSCSo9liUWCVzyDWA X-IronPort-AV: E=Sophos;i="4.65,453,1304287200"; d="scan'208";a="86377959" Received: from mail-vx0-f182.google.com ([209.85.220.182]) by mail3-smtp-sop.national.inria.fr with ESMTP/TLS/RC4-SHA; 30 Jun 2011 19:26:53 +0200 Received: by vxg33 with SMTP id 33so3361311vxg.27 for ; Thu, 30 Jun 2011 10:26:52 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc:content-type; bh=lodP+RCtdHwd6fDquMRJ61D0k7jiD46dnU7dWg3E4qU=; b=VIQh6lN3e/+OEV0NJLlCpRDYbaiQTI5LbEqsc+h4ee+/wxZ5DpKWznG6KjWOzjaPuZ VzSD7JiTF6835a9dLsUH0QBk2GbRRe/YgZiXs54Y/ApZpZHnBPCADUkagUo7jpEt4eTQ lr1F++JSqx6rQUGSdGDKv7tpD/HCIaOIkP8gw= Received: by 10.52.19.161 with SMTP id g1mr3326977vde.11.1309454812234; Thu, 30 Jun 2011 10:26:52 -0700 (PDT) MIME-Version: 1.0 Received: by 10.52.168.73 with HTTP; Thu, 30 Jun 2011 10:26:32 -0700 (PDT) In-Reply-To: <4E0CAEC3.7010804@gmail.com> References: <4E0CAEC3.7010804@gmail.com> From: Gabriel Scherer Date: Thu, 30 Jun 2011 19:26:32 +0200 Message-ID: To: Andrew Cc: caml-list@inria.fr Content-Type: multipart/alternative; boundary=20cf307c9c2eeec53104a6f134a3 Subject: Re: [Caml-list] Priority queues, reloaded --20cf307c9c2eeec53104a6f134a3 Content-Type: text/plain; charset=ISO-8859-1 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. 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 > > --20cf307c9c2eeec53104a6f134a3 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable The heap implementation in the OCaml manual, which was pointed to in the pr= ecedent thread, is quite compact.

Okasaki (eg. in its book "Pur= ely functional data structure", but can probably be found in papers av= ailable on the net) has a "leftist heap" data structure that is a= lso compact and, to my personal taste, easier to understand, get familiar w= ith 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 impleme= nt both his leftist heap and the red-black trees in around 15 minutes.

On Thu, Jun 30, 2011 at 7:13 PM, Andrew <newsgroups.fr@gmail.com> wrote:
Hi all,

Since the previous discussion regarding priority queues pretty much conclud= ed that they weren't available in OCaml, could you point to the most co= mpact implementation that you know of? I'm very likely to have to recod= e my own implementation in a time-restricted setting, so I'd love to he= ar about efficient-yet-easy/fast-to-implement options.

Thanks!

--
Caml-list mailing list. =A0Subscription management and archives:
https://sympa-roc.inria.fr/wws/info/caml-list
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners<= /a>
Bug reports: http://caml.inria.fr/bin/caml-bugs


--20cf307c9c2eeec53104a6f134a3--