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 p62KscUM013651 for ; Sat, 2 Jul 2011 22:54:39 +0200 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: ArkDAA+FD07RVdy2mGdsb2JhbABSmFwzjmoIFAEBAQEBCAkNBxQliHqkQZtphjYEnlk8g3M X-IronPort-AV: E=Sophos;i="4.65,465,1304287200"; d="scan'208";a="86479873" Received: from mail-vx0-f182.google.com ([209.85.220.182]) by mail3-smtp-sop.national.inria.fr with ESMTP/TLS/RC4-SHA; 02 Jul 2011 22:54:33 +0200 Received: by vxg33 with SMTP id 33so5644628vxg.27 for ; Sat, 02 Jul 2011 13:54:31 -0700 (PDT) Received: by 10.220.148.66 with SMTP id o2mr1773348vcv.93.1309640070219; Sat, 02 Jul 2011 13:54:30 -0700 (PDT) Received: from sergyar.local (pool-96-246-9-191.nycmny.east.verizon.net [96.246.9.191]) by mx.google.com with ESMTPS id v3sm815669vcg.23.2011.07.02.13.54.28 (version=TLSv1/SSLv3 cipher=OTHER); Sat, 02 Jul 2011 13:54:29 -0700 (PDT) Date: Sat, 2 Jul 2011 16:54:27 -0400 (EDT) From: Brian Hurt X-X-Sender: bhurt@sergyar To: fa.caml@googlegroups.com cc: caml-list@inria.fr, Jean-Christophe.Filliatre@lri.fr In-Reply-To: <0bb28c99-9ffd-4b5d-b073-8aff7af00493@glegroupsg2000goo.googlegroups.com> Message-ID: References: <0bb28c99-9ffd-4b5d-b073-8aff7af00493@glegroupsg2000goo.googlegroups.com> User-Agent: Alpine 2.02 (DEB 1266 2009-07-14) MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed Subject: Re: [Caml-list] Priority queues On Fri, 1 Jul 2011, Radu Grigore wrote: > On Friday, July 1, 2011 11:33:11 AM UTC+1, Andrew wrote: >>> - or your priority queue does not provide such an operation, and you >>> simply add another entry for y in the priority queue, with a different >>> key. It means you have now several entries for y in the priority queue. >>> The better will be extracted first; the others will be ignored when they >>> are extracted later. Complexity is now O(E log(V)). >> >> Just an extra question though: How come it's not O(E log (E))? >> You could end up pushing as much as one new element in >> your heap per edge, couldn't you? > > If you use a Set of (distance, vertex) pairs together with min_elt then > you can simulate decrease-key using remove followed by add. You could also keep a map of vertices to distances, so you can update the distance of a vertex that is not the minimum element without knowing what it's previous distance was. Something like: module PQ(Key: Map.Ordered)(Data: Map.Ordered) = struct module X = struct type t = Key.t * Data.t;; let compare (k1, d1) (k2, d2) = let c = Key.compare k1 k2 in if (c != 0) then c else Data.compare d1 d2 end module Y = Set.make(X) module Z = Map.make(Data) type t = Y.t * (Key.t Z.t) let empty : t = Y.empty, Z.empty let add (s, m) k d = try let k' = Z.find d m in let s = Y.remove (k', d) s in let s = Y.add (k, d) s in let m = Z.add d k m in (s, m) with | Not_found -> let s = Y.add (k, s) s in let m = Z.add d k m in (s, m) let head (s, _) -> snd (Y.min_elt s) end;; All the other operations should be obvious. Brian > > -- > Caml-list mailing list. Subscription management and archives: > https://sympa-roc.inria.fr/wws/info/caml-list > Beginner's list: http://groups.yahoo.com/group/ocaml_beginners > Bug reports: http://caml.inria.fr/bin/caml-bugs > >