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!
- The Iowa Logic
Simulator is a digital logic simulator that uses a discrete event
simulation model implemented using pairing heaps.