Splay Trees
Splay-trees, a form of self-adjusting binary search tree invented by
Dan Sleator and analyzed by Bob Tarjan, have proven to be one of the
fastest and most robust implementations of the pending-event set, the
central abstraction underlying the sequential discrete event simulation
algorithm.
The pending-event set is basically a priority queue, where the act of
scheduling an event to take place at some future time inserts an event
notice in the priority queue, and the main simulation loop proceeds by
repeatedly extracting from the pending-event set the event notice with
minimum time.
Other Event Sets and Priority Queues
- Eleven
algorithms in Pascal. This collection of algorithms was the basis
of the paper
An Empirical Comparison
of Priority Queue and Event Set Implementations
in Communications of the ACM, 29, April 1986,
pages 300-311. This paper was the first to show the speed and stability
of the splay-tree data structure. The following data structures are
included here: Linear linked list, leftist trees, Blackstone's two-list
structure, implicit heaps, Henriksen's indexed list, binomial queues,
pagodas, bottom-up skew heaps, top-down skew heaps,
splay trees, and pairing heaps.
- Lee
Killough's priority queue web page provides an up-to-date variation on this
collection!
Other Discrete Event Simulation
- The Iowa Logic
Simulator is a digital logic simulator originally written in Pascal
that uses a discrete-event simulation model implemented using pairing heaps.
- An Epidemic Simulator
is a discrete-event simulation written in Java, including a simulation framework
based on Java's class PriorityQueue using lambda expressions to pass
the events associated with events.