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 p62MgFYe015982 for ; Sun, 3 Jul 2011 00:42:15 +0200 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: Ao8GAKydD07RVdo+lGdsb2JhbABSmQ+OaggUAQEBAQkJCwkSJ61CjCaGFzmIbYY2BIc/g2KTODyDdw X-IronPort-AV: E=Sophos;i="4.65,465,1304287200"; d="scan'208";a="86482211" Received: from mail-yi0-f62.google.com ([209.85.218.62]) by mail3-smtp-sop.national.inria.fr with ESMTP/TLS/RC4-SHA; 03 Jul 2011 00:42:09 +0200 Received: by yic15 with SMTP id 15so3994006yic.27 for ; Sat, 02 Jul 2011 15:42:07 -0700 (PDT) Received: by 10.101.188.15 with SMTP id q15mr465483anp.2.1309646527674; Sat, 02 Jul 2011 15:42:07 -0700 (PDT) Path: glegroupsg2000goo.googlegroups.com!not-for-mail Newsgroups: fa.caml Date: Sat, 2 Jul 2011 15:42:07 -0700 (PDT) In-Reply-To: <30775f1d-9cce-4c46-b7f0-62cdcf9e52cf@glegroupsg2000goo.googlegroups.com> Reply-To: fa.caml@googlegroups.com Complaints-To: groups-abuse@google.com Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=188.221.185.251; posting-account=e5mzsQoAAAB7g9y7Bkgam0zJDHRr7bCB NNTP-Posting-Host: 188.221.185.251 User-Agent: G2/1.0 X-Google-Web-Client: true MIME-Version: 1.0 Message-ID: <43c8bcb0-e306-421f-a379-43dd4e7de4a0@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 p62MgFYe015982 Subject: Re: [Caml-list] Priority queues, reloaded I asked: > How is that [a leftist heap implementation] better than using Set? and Andrew answered: > Sets are not heaps ; they can't have multiple copies of the same element. I asked my question in the context of Andrew's original query: > I'd love to hear about efficient-yet-easy/fast-to-implement options. I meant to ask why would it be easier/faster to implement a leftist heap. Of course, if leftist heaps can do something that an implementation based on Set can't then that would be a problem. Also, if an implementation based on Set would be much slower or memory hungry, that would also be a problem. But it was already explained by others for Dijsktra at least the lack of Decrease-Key is not a problem, and (asymptotic) performance is not an issue. You now bring up the question of multiplicity, which may be important if you try to, say, find the top K elements in a stream. Again, a Set based implementation is much simpler than the leftist heaps that were posted already. Here it is. module S = Set.Make (struct type t = int*int*int let compare = compare end) let uid = ref 0 let push pq p x = incr uid; S.add (p, x, !uid) pq let pop pq = let (_,x,_) as k = S.min_elt pq in (x, S.remove k, pq) 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.