Simulation Pending-Event-Set Implementations

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.

• the original Pascal code. Most implementations of splay trees in use today are descended from this code.
• Dave Brower's C code. A widely used C transliteration of the above Pascal code. Dave Brower's book on data structures has a chapter based on this.
• An Ada generic package. This is also derived from the above, and has seen considerable use. See also: Kennisaw Iowa State

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.