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