An empirical comparison of priority-queue and event-set implementations

ABSTRACT

Execution times for a variety of priority-queue implementations are compared under the hold model, showing many to be faster than implicit heaps.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: Jon Bentley, Programming pearls: thanks, heaps, Communications of the ACM, v.28 n.3, p.245-250, March 1985 [doi>10.1145/3166.315010]
• 3: John H. Blackstone, Jr. , Gary L. Hogg , Don T. Phillips, A two-list synchronization procedure for discrete event simulation, Communications of the ACM, v.24 n.12, p.825-829, Dec. 1981 [doi>10.1145/358800.358805]
• 4: Brown, M.R. The analysis of a practical and nearly optimal priority queue. Comput. Sci. Rep. STAN-CS-77-600, Dept. of Computer Science, Stanford Univ., Calif., Mar. 1977. This is the same as {5}, but with an appendix containing working SAIL code.
• 5: Brown, M.R. Implementation and analysis of binomial queue algorithms. SIAM 1. Comput. 7.3 (Aug. 1976). 298-319. An assortment of implementations of binomial queues is presented along with a detailed performance analysis and empirical comparisons with leftist trees and heaps.
• 6: Francon. J., Viennot, G., and Vuillemin, J. Description and analysis of an efficient priority queue representation. In Proceedings of the 19th Annual Symposium on Foundations of Computer Science (Ann Arbor, Mich.. Oct. 16-18). IEEE, Piscataway, N.J.. 1978, pp. Z-7. (Also published as IRIA Rapport de Recherche No 287.) The original presentation of pagodas.
• 7: W. R. Franta , Kurt Maly, A comparison of heaps and the TL structure for the simulation event set, Communications of the ACM, v.21 n.10, p.873-875, Oct. 1978 [doi>10.1145/359619.359637]
• 8: Fredman, M.L., Sedgewick, R., Sleator. D.. and Tarjan, R. The pairing heap: A new form of self-adjusting heap. Submitted for publication. Pairing heaps and their variants are described and analyzed.
• 9: Geoffrey Gordon, The development of the General Purpose Simulation System (GPSS), ACM SIGPLAN Notices, v.13 n.8, p.183-198, August 1978 [doi>10.1145/960118.808382]
• 10: James O. Henriksen, An improved events list algorithm, Proceedings of the 9th conference on Winter simulation, p.546-557, December 05-07, 1977, Gaitersburg, MD
• 11: James O. Henriksen, Event list management - a tutorial, Proceedings of the 15th conference on Winter Simulation, p.543-551, December 12-14, 1983, Arlington, Virginia, United States
• 12: Jonassen, A. Priority queue processes with biased insertion of exponentially distributed input keys. Rep. 14, Univ. of Oslo Institute of Informatics, Norway, May 1977, ISBN 82-90230-02-8. Clear description of the hold model. Proof that the exponential distribution results in a uniform insertion distribution in the steady state.
• 13: Jonassen, A., and Dahl, O.J. Analysis of an algorithm for priority queue administration. BIT 15, 4 (1975). 409422. Presents the p-tree algorithm, an analysis (later disputed in {15}), and comparisons under the hold model with implicit heaps, leftist trees, AVL-trees, and linear lists.
• 14: Jones, D.W. Concurrent operations on priority queues. Submitted for publication. Skew heaps allow priority-queue operations in O(1) time given O(log n) processors in a shared-memory environment.
• 15: Kingston, J.H. Analysis of algorithms for the simulation event list. Ph.D. thesis, Basser Dept. of Computer Science, Univ. of Sydney, Australia, July 1984. Average case analysis of binary trees, p-trees, and Henriksen's under the hold model.
• 16: Jeffrey H. Kingston, Analysis of tree algorithms for the simulation event list, Acta Informatica, v.22 n.1, p.15-33, April 1985 [doi>10.1007/BF00290143]
• 17: Kingston, J.H. The amortized complexity of Henriksen's algorithm. Comput. Sci. Tech. Rep. 85-06, Dept. of Corn P uter Science, Univ. of Iowa, Iowa City, July 1985. Proof of an O(n' ') amortized bound.
• 18: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 19: William M. McCormack , Robert G. Sargent, Analysis of future event set algorithms for discrete event simulation, Communications of the ACM, v.24 n.12, p.801-812, Dec. 1981 [doi>10.1145/358800.358803]
• 20: Nix, R. An evaluation of pagodas. Res. Rep. 164, Dept. of Computer Science, Yale Univ., New Haven, Conn., no date. Analysis and empirical comparisons with binomial queues, heaps, and leftist trees. Well-commented PDP-10 assembly language code is given.
• 21: Daniel Dominic Sleator , Robert Endre Tarjan, Self-adjusting binary trees, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.235-245, December 1983 [doi>10.1145/800061.808752]
• 22: Daniel Dominic Sleator , Robert Endre Tarjan, Self adjusting heaps, SIAM Journal on Computing, v.15 n.1, p.52-69, Feb. 1986 [doi>10.1137/0215004]
• 23: Daniel Dominic Sleator , Robert Endre Tarjan, Self-adjusting binary search trees, Journal of the ACM (JACM), v.32 n.3, p.652-686, July 1985 [doi>10.1145/3828.3835]
• 24: Jean Vuillemin, A data structure for manipulating priority queues, Communications of the ACM, v.21 n.4, p.309-315, April 1978 [doi>10.1145/359460.359478]
• 25: Williams, J.W.J. Algorithm 232: Heapsort. Commun. ACM 7, 6 (June 1964), 347-348. Original presentation of implicit heaps.

INDEX TERMS

Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees
  E.2 DATA STORAGE REPRESENTATIONS
      Subjects: Linked representations

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.1 Simulation Theory
          Subjects: Types of simulation (continuous and discrete)*

General Terms:
Algorithms, Measurement, Performance