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 p62CP3YW004615 for ; Sat, 2 Jul 2011 14:25:03 +0200 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: Aq4AAIsND07RVaG+jmdsb2JhbABSmE1CjmoIFAEBAQEJCxISBiGIeqVTjCaGPTmIbYY2BIc/g2KTODyDdw X-IronPort-AV: E=Sophos;i="4.65,463,1304287200"; d="scan'208";a="86470744" Received: from mail-gx0-f190.google.com ([209.85.161.190]) by mail3-smtp-sop.national.inria.fr with ESMTP/TLS/RC4-SHA; 02 Jul 2011 14:24:58 +0200 Received: by gxk7 with SMTP id 7so3651248gxk.27 for ; Sat, 02 Jul 2011 05:24:56 -0700 (PDT) Received: by 10.91.195.19 with SMTP id x19mr15842agp.28.1309609496743; Sat, 02 Jul 2011 05:24:56 -0700 (PDT) Path: glegroupsg2000goo.googlegroups.com!not-for-mail Newsgroups: fa.caml Date: Sat, 2 Jul 2011 05:24:56 -0700 (PDT) In-Reply-To: Reply-To: fa.caml@googlegroups.com Complaints-To: groups-abuse@google.com Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=138.37.88.134; posting-account=e5mzsQoAAAB7g9y7Bkgam0zJDHRr7bCB NNTP-Posting-Host: 138.37.88.134 User-Agent: G2/1.0 X-Google-Web-Client: true MIME-Version: 1.0 Message-ID: <30775f1d-9cce-4c46-b7f0-62cdcf9e52cf@glegroupsg2000goo.googlegroups.com> From: Radu Grigore To: fa.caml@googlegroups.com Cc: caml-list@inria.fr Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by walapai.inria.fr id p62CP3YW004615 Subject: Re: [Caml-list] Priority queues, reloaded On Thursday, June 30, 2011 7:14:56 PM UTC+1, Jean-Christophe Filliâtre wrote: > 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 [...] Okasaki probably prefers maxiphobic heaps. http://www.eecs.usma.edu/webs/people/okasaki/sigcse05.pdf > I confirm that leftist heap is probably the best possible choice. How is that better than using Set? The only reason I see for implementing your own heap is to save space: Binomial heaps have much better constants. (Smaller space & cache will likely lead to less time.)