aliao@eagle.wesleyan.edu (09/28/90)
My thanks to all those who responded to my query. Below are the
responses that attempted to address my question. It appears that
most of the reponses centered around the splay trees though
FHeaps, skew and pairing heaps were briefly mentioned. I thought
I'd post these now since I am going on holiday for two weeks.
Once again, my thanks. -drew liao
*** *** *** *** *** *** *** *** ***
From: dietz@cs.rochester.edu
Talk to Dave Johnson at Bell Labs. He and coworkers (Lyle McGeoch,
for one) have been programming heuristics for planar traveling salesman
for very large N (10^6 and more). Splay trees are useful for
representing tours, since they let you efficiently implement
"flip a segment of the tour" and "does b fall between a and c on the tour"
operations.
There was a paper at the last ICALP; I don't remember if it went
into detail about the data structures.
Paul F. Dietz
dietz@cs.rochester.edu
From: Ira Baxter <baxter@zola.ICS.UCI.EDU>
I used splay trees in a best-first search application; seemed to work
nicely. Most of the application I have seen discussed is
simulation; there's an article by Doug? Jones in CACM, middle to late
80's on such applications.
I like them. But I'm not really a theoretician.
--
Ira Baxter
From: moret@cmell.cs.unm.edu
Henry Shapiro and I have run large-scale comparisons of minimum
spanning tree algorithms, using a variety of implementations.
One of them is the lazy leftist heap of Tarjan, used in the
Cheriton-Tarjan algorithm; others include Fibonacci heaps.
d-heaps, etc. Lazy leftist trees appear quite effective,
although they are very wasteful of memory; our conclusion is that
Fibonacci heaps and lazy leftist heaps are too slow for sizes
below 10-50,000 nodes. (Results of the experiments appear in
Chapter 5 of our soon-to-appear text---Nov. 90---on algorithms,
``Algorithms from P to NP, Vol. I: Design and Efficiency,'' at
Benjamin-Cummings.) In separate experiments, we compared pairing
heaps, skew heaps, leftist and lazy leftist heaps, binomial
queues, and Fibonacci heaps (we wanted to include relaxed
heaps---Driscoll, Tarjan, et al.---but quickly realized that the
overhead makes them completely useless), as well as splay trees,
"standard heaps", and various balanced trees (AVL, red-black,
2-3). If melding is not important, then standard heaps win hands
down, even when DecreaseKey is included; otherwise, splay trees
seem as fast as anything else and more flexible. (We'd appreciate
a copy of any other/different results you hear of or obtain.)
Bernard M.E. Moret Department of Computer Science
(505) 277-31{31,12} University of New Mexico, Albuquerque, NM 87131
moret@unmvax.unm.edu (ID number of unmvax.unm.edu is 129.24.12.128)
From: "Douglas W. Jones" <jones@pyrite.cs.uiowa.edu>
Splay trees are widely used, as a result of the inclusion of a
(slightly buggy) implementation of splay trees in the Gnu C++
distribution from the Free Software Foundation. The bug is that
you can't delete the last item in the tree; this bug results from
an error in transliteration from my Pascal code to C by Dave
Brower at Sun Microsystems, he fixed the bug a long time ago, but
for some reason the people at Gnu seem to have taken their time
passing on the fix to C++ users.
I've been using pairing heaps in my digital logic simulator since
June 1985, not because they are best, but merely because they are
about as good as any of the other good algorithms, and it seemed
that someone ought to use them in a production application.
I've distributed copies of the code for the queue implementations
described in my CACM paper to about 30 different investigators,
most of whom were simply looking for fast code, although a few
used them for instructional purposes or for comparison with the
results of their own algorithm research.
Also, the splay-tree based data compression code I developed has
been very widely distributed. I don't know who uses it in
production, but for a while, when people were talking about
patent problems with LZW compression, it became a candidate
alternative to the UNIX compress command.
Doug Jones
jones@herky.cs.uiowa.edu