Re: [Caml-list] Priority queues

[Brian Hurt <bhurt@spnz.org>]

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
>
>