A taxonomy and analysis of event set management algorithms for discrete event simulation
John Craig Comfort · Annual Simulation Symposium · 1979
Seven event set management algorithms and their associated data structure are presented informally and formally, their performances (time per “hold” operation, search length) are analyzed empirically, using appropriate statistical tests, and the relations between these algorithms are discussed. Each algorithm is tested for several different inter-arrival distributions and event set sizes. Five of these algorithms use data structures which apply successively more sophisticated indexing to a basic linked list, resulting in two algorithms with nearly constant assymptotic behavior. The other two, based on the “heap” data structure, has logarithmic behavior.