RE: RE: [Caml-list] Priority queues, reloaded

["Jon Harrop" <jon@ffconsultancy.com>]

Radu Grigore wrote:
> Another comparison appears in SGB, file miles_span.w, in the context of
> computing minimum spanning trees. It turns out that Fibonacci heaps are
not
> only a theoretical curiosity!

That's interesting. I was under the impression Fibonacci heaps had a really
bad constant prefactor.

If this is the right file:

  http://ftp.sunet.se/pub/text-processing/TeX/support/graphbase/miles_span.w

Then they say:

  "We will try out four basic algorithms that have received prominent
attention in the literature. Graham and Hell's Algorithm~1 is represented
by the |krusk| procedure, which uses Kruskal's algorithm after the
edges have been sorted by length with a radix sort. Their Algorithm~2
is represented by the |jar_pr| procedure, which incorporates a 
priority queue structure that we implement in two ways, either as
a simple binary heap or as a Fibonacci heap. And their Algorithm~3
is represented by the |cher_tar_kar| procedure, which implements a
method similar to Bor{\accent23u}vka's that was independently
discovered by Cheriton and Tarjan and later simplified by Karp and Tarjan. "

So they're only comparing binary and Fibonacci heaps (not skew, leftist,
pairing, binomial etc). Moreover, do you actually need a heap in the MST
algorithm? You cannot add the shortest edge first without traversing all
edges so you must consider all edges. I suppose a heap could win out over a
sort if the MST only requires a small proportion of all the edges, i.e.
finding the 1..k shortest edges, but I'm not sure how valuable that is in
practice.

Regardless, I'm sure the first step in optimizing such algorithms is to
sacrifice purity. :-)

Cheers,
Jon.