From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by walapai.inria.fr (8.13.6/8.13.6) with ESMTP id p6BCtlKT027591 for ; Mon, 11 Jul 2011 14:55:47 +0200 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AqkAAALyGk5KfVM+i2dsb2JhbABTmAJDjmwIFAEBAQoLCwcSBiGIeqMZjCyGXTuIbYY6BIdOg2WTUjyDeg X-IronPort-AV: E=Sophos;i="4.65,515,1304287200"; d="scan'208";a="98345066" Received: from mail-gw0-f62.google.com ([74.125.83.62]) by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/RC4-SHA; 11 Jul 2011 14:55:41 +0200 Received: by gwj22 with SMTP id 22so3624506gwj.27 for ; Mon, 11 Jul 2011 05:55:40 -0700 (PDT) Received: by 10.101.168.22 with SMTP id v22mr527633ano.34.1310388940467; Mon, 11 Jul 2011 05:55:40 -0700 (PDT) Path: glegroupsg2000goo.googlegroups.com!not-for-mail Newsgroups: fa.caml Date: Mon, 11 Jul 2011 05:55:40 -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: From: Radu Grigore To: fa.caml@googlegroups.com Cc: caml-list@inria.fr Content-Type: text/plain; charset=ISO-8859-1 Subject: Re: RE: [Caml-list] Priority queues, reloaded On Sunday, July 10, 2011 6:55:57 PM UTC+1, Jon Harrop wrote: > > In a real program, I'd probably go for binomial heaps if imperative is OK, > FWIW, I found that Okasaki's binomial heaps are among the slowest. Oops. I meant (imperative) *binary* heaps (the ones that stay in an array and don't need explicit pointers to parents/children to save memory---that's why I was mentioning space use). It's not the first time I say binomial instead of binary ... > Pairing > heaps were the fastest overall, closely followed by leftist heaps in OCaml. > If elements are inserted in order then the leftist heap is ~3x slower than a > pairing heap in OCaml and ~5x slower in F#. Good to know! Another comparison appears in SGB, file miles_span.w, in the context of computing minimum spanning trees. It turns out that Fibonacci heaps are not only a theoretical curiosity!