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 p62J5Vr6011707
	for <caml-list@sympa-roc.inria.fr>; Sat, 2 Jul 2011 21:05:31 +0200
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: Al0AAD1rD05KfVK2kGdsb2JhbAA8AQMSmE2OSmIIFAEBAQEJCQ0HFAQhiHykW4wmgkyDWjmIaAIDBoYwBJI2hHiBHYYOPINZ
X-IronPort-AV: E=Sophos;i="4.65,464,1304287200"; 
   d="scan'208";a="86478062"
Received: from mail-wy0-f182.google.com ([74.125.82.182])
  by mail3-smtp-sop.national.inria.fr with ESMTP/TLS/RC4-SHA; 02 Jul 2011 21:05:25 +0200
Received: by wyg24 with SMTP id 24so5044114wyg.27
        for <caml-list@inria.fr>; Sat, 02 Jul 2011 12:05:25 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=gmail.com; s=gamma;
        h=message-id:date:from:user-agent:mime-version:cc:subject:references
         :in-reply-to:content-type:content-transfer-encoding;
        bh=QFgmig6SIBSRzQMmPH7z/aneOID6LFLBNRJkoE1/yg8=;
        b=dwlV/WqX4SIdi8zZfT59fjus2W58omCOlNqtbqtWFnBqovUiWICScejs5CbQ8F3fxB
         r6X6gE5pvn4X+CpmJjyGyGoD/agXtekEWNcSpFfCm1Xns7I21JjV9jb9j9o/PzNWar45
         k8Cb92hG98tOxSEeuEk43ElmLoTL+2nsY9BeI=
Received: by 10.227.157.134 with SMTP id b6mr4073681wbx.59.1309633525370;
        Sat, 02 Jul 2011 12:05:25 -0700 (PDT)
Received: from [192.168.1.186] (106.165.7.93.rev.sfr.net [93.7.165.106])
        by mx.google.com with ESMTPS id et5sm3185892wbb.16.2011.07.02.12.05.23
        (version=SSLv3 cipher=OTHER);
        Sat, 02 Jul 2011 12:05:24 -0700 (PDT)
Message-ID: <4E0F6BF7.5010605@gmail.com>
Date: Sat, 02 Jul 2011 21:05:27 +0200
From: Andrew <newsgroups.fr@gmail.com>
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:5.0) Gecko/20110624 Thunderbird/5.0
MIME-Version: 1.0
CC: Radu Grigore <radugrigore@gmail.com>, caml-list@inria.fr
References: <30775f1d-9cce-4c46-b7f0-62cdcf9e52cf@glegroupsg2000goo.googlegroups.com>
In-Reply-To: <30775f1d-9cce-4c46-b7f0-62cdcf9e52cf@glegroupsg2000goo.googlegroups.com>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 8bit
Subject: Re: [Caml-list] Priority queues, reloaded

Radu Grigore wrote:
> 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.)
>

Sets are not heaps ; they can't have multiple copies of the same element.