Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!ns-mx!pyrite.cs.uiowa.edu
From: jones@pyrite.cs.uiowa.edu (Douglas W. Jones,201H MLH,3193350740,3193382879)
Newsgroups: comp.theory
Subject: Re: data structures of Tarjan, et.al and actual applications?
Message-ID: <2430@ns-mx.uiowa.edu>
Date: 24 Sep 90 20:31:05 GMT
References: <1990Sep23.193541.33486@eagle.wesleyan.edu>
Sender: news@ns-mx.uiowa.edu
Lines: 25

From article <1990Sep23.193541.33486@eagle.wesleyan.edu>,
by aliao@eagle.wesleyan.edu:

> Has anyone else been using the data structures that Bob Tarjan, et. al
> in any actual applications?

In the logic simulator I use for teaching a digital logic class, I've been
using pairing heaps for the last 5 years, largely because they are as good
as anything else for my purposes, and it seemed that someone ought to be
using that data structure.  This counts as a production application, in
that the student users never see the source code.

Dave Brower of Sun Microsystems transliterated my Pascal version of splay
trees to C some time ago, and an early version of his transliteration is
in the Gnu C++ library.  Unfortunately, that version has a bug (it won't
delete the last item from a tree!) but I gather it's been fairly widely
used with no complaints (because few people delete randomly in a tree, I
guess).

My splay-tree based compression algorithm has been widely distributed,
but I don't know if anyone actually uses it in any production application.
There are many others I've been in touch with, but I've lost track of them.

					Doug Jones
					jones@herky.cs.uiowa.edu