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 p6AHtcmG016959
	for <caml-list@sympa-roc.inria.fr>; Sun, 10 Jul 2011 19:55:38 +0200
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: Ar0CAKXmGU7UnwckkGdsb2JhbABTmEmOcxQBAQEBCQkNBxQEIYh8wAaGOgSXUotK
X-IronPort-AV: E=Sophos;i="4.65,509,1304287200"; 
   d="scan'208";a="98301536"
Received: from relay.ptn-ipout02.plus.net ([212.159.7.36])
  by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/RC4-SHA; 10 Jul 2011 19:55:33 +0200
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: AkYGANLmGU7Unw4S/2dsb2JhbABTmEmOc3eIfMAHhjoEl1KLSg
Received: from outmx06.plus.net ([212.159.14.18])
  by relay.ptn-ipout02.plus.net with ESMTP; 10 Jul 2011 18:55:32 +0100
Received: from [87.113.101.205] (helo=WinEight)
	 by outmx06.plus.net with esmtp (Exim) id 1QfyE7-0004C2-LZ
	for caml-list@inria.fr; Sun, 10 Jul 2011 18:55:31 +0100
From: "Jon Harrop" <jon@ffconsultancy.com>
To: <caml-list@inria.fr>
References: <30775f1d-9cce-4c46-b7f0-62cdcf9e52cf@glegroupsg2000goo.googlegroups.com> <43c8bcb0-e306-421f-a379-43dd4e7de4a0@glegroupsg2000goo.googlegroups.com>
In-Reply-To: <43c8bcb0-e306-421f-a379-43dd4e7de4a0@glegroupsg2000goo.googlegroups.com>
Date: Sun, 10 Jul 2011 18:55:10 +0100
Message-ID: <02a901cc3f2a$83cb0b00$8b612100$@ffconsultancy.com>
MIME-Version: 1.0
Content-Type: text/plain;
	charset="us-ascii"
Content-Transfer-Encoding: 7bit
X-Mailer: Microsoft Outlook 14.0
Thread-Index: AQEgG/EiR2gxpzcRaS5+zQ1s7Lp3A5Y+HAvg
Content-Language: en-gb
Subject: RE: [Caml-list] Priority queues, reloaded

Radu Grigore wrote:
> With a time limit of three hours this is what I'd do. In a real program,
I'd
> probably go for binomial heaps if imperative is OK, or maxiphobic heaps if
> persistence is important.

FWIW, I found that Okasaki's binomial heaps are among the slowest. 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#.

Cheers,
Jon.