Re: binary heap

[jones@pyrite.cs.uiowa.edu (Douglas W. Jones,201H MLH,3193350740,3193382879)]

In article <CzA7FF.K7s@inmet.camb.inmet.com>,
Tucker Taft <stt@spock.camb.inmet.com> wrote:
 
>Here is some Ada 83 code for a binary heap used to implement a priority 
>queue (FIFO within priority); this code (or a slight variation of it)
>has been used successfully for many years.

But note that the binary heap, by the benchmarks I published some years
ago, is about a factor of 2 slower than splay trees under the hold model
(repeated steady-state insertion and deletion in a priority queue), and
note that the heap requires that you know the maximum size of the
priority queue in advance.  Splay trees, being based on binary trees,
are limited only by available memory.

You can get my code from the STARS library or from:

	ftp://ftp.cs.uiowa.edu/pub/jones/event/splayada.txt.Z

This is a generic Ada package.  Although it's written and documented in
terms of discrete event simulation, it is easy to use as a general puprose
priority queue (the generic parameter TIME_TYPE is the type to be used
for the priority field; all that is required is that there be an ">"
operator.  The generic parameter AUX_TYPE is the data enqueued in the
priority queue.
				Doug Jones
				jones@cs.uiowa.edu