Re: [Caml-list] Priority queues, reloaded

[Radu Grigore <radugrigore@gmail.com>]

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.