A data structure for manipulating priority queues

ABSTRACT

A data structure is described which can be used for representing a collection of priority queues. The primitive operations are insertion, deletion, union, update, and search for an item of earliest priority.

REFERENCES

• 1: Adel'son-Vel'skii, G.M., and Landis, Y.M. An algorithm for the organisation of information. Dokl. Akad. Nauk. SSSR 146, (1962), 263-266.
• 2: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 3: Brown, M.R. Implementation and analysis of binomial queue algorithms. (to appear in SICOMP).
• 4: Cberiton, D., Tarjan, R.E., Yao, A.C. Finding minimum spanning trees. Res. Rep. Dept. Comptr. Sci. Stanford U., Stanford, Calif., 1975; also S1AMJ. Comptng. 5, 4 (Dec. 1976), 724-742.
• 5: Crane, C.A. Linear lists and priority queues as balanced binary trees. Rep. Stan-CS-72-259, Dept. Comptr. Sci., Stanford U., Stanford, Calif., 1972.
• 6: Fischer, M.J. Efficiency of equivalence algorithms. In Complexity of Computer Computations, R.E. Miller and J.W. Thatcher, Eds., Plenum Press, New York, 1972, pp. 158-168.
• 7: Robert W. Floyd, Algorithm 245: Treesort, Communications of the ACM, v.7 n.12, p.701, Dec. 1964 [doi>10.1145/355588.365103]
• 8: Ford, L.R., and Johnson, S.M. A tournament problem. Amer. Math. Monthly 66 (1959), 387-389.
• 9: Fran~on, J. Representation d'une file de priorit~s par un arbre binaire. Rapport, Dept. Math., U. de Strasbourg, 1975.
• 10: Gentleman, W.M. Row elimination for solving sparse linear systems and least squares problems. Dundee Biennial Conf. on Numer. Anal., 1975.
• 11: Gaston H. Gonnet, Heaps applied to event driven mechanisms, Communications of the ACM, v.19 n.7, p.417-418, July 1976 [doi>10.1145/360248.360261]
• 12: Gonnet, G.H., and Rogers, L.D. An algorithmic and complexity analysis of the heap as a data structure. Res. Rep. CS 75-20, U. of Waterloo, Waterloo, Canada, 1975.
• 13: Donald Bruce Johnson, Algorithms for shortest paths., 1973
• 14: Johnson, D.B. Priority queues with update and finding minimum spanning trees. Tech. Rep. 170, Penn. State U., University Park, Pa., 1975.
• 15: Jonassen, A., and Dahl, O.J. Analysis of an algorithm for priority queue administration. BIT 15 (1975), 409-422.
• 16: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 17: 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
• 18: Donald Ervin Knuth, Selected Papers on Computer Science, CSLI Publications, Stanford, CA, 1995
• 19: Michael A. Malcolm , R. Bruce Simpson, Local Versus Global Strategies for Adaptive Quadrature, ACM Transactions on Mathematical Software (TOMS), v.1 n.2, p.129-146, June 1975 [doi>10.1145/355637.355640]
• 20: A. Schonhage , M. S. Paterson , N. Pippenger, Finding the Median, University of Warwick, Coventry, UK, 1975
• 21: Thomas Porter , Istvan Simon, Random insertion into a priority queue structure., Stanford University, Stanford, CA, 1974
• 22: Prim, R. C. Shortest connection networks and some generalizations. Bell Syst. Tech. J. 36, 6 (1957), 1389-1401.
• 23: van Emde Boas, B.P., Kaas, R., and Zijlstra, E. Design and implementation of an efficient priority queue. Math. Centrum Rep. ZW 60/75, Amsterdam, 1975.
• 24: Jean G. Vaucher , Pierre Duval, A comparison of simulation event list algorithms, Communications of the ACM, v.18 n.4, p.223-230, April 1975 [doi>10.1145/360715.360758]
• 25: Vuillemin, J. Structures de donndes. Notes de cours de l'ecole d'&6, CEA-EDF-IRIA, 1975.
• 26: Williams, J.W.J. Algorithm 232. Heapsort. Comm. ACM 7, 6 (June 1964), 347-348.
• 27: F. Paul Wyman, Improved event-scanning mechanisms for discrete event simulation, Communications of the ACM, v.18 n.6, p.350-353, June 1975 [doi>10.1145/360825.360873]

INDEX TERMS

Primary Classification:
  E. Data

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.8 Performance
          Subjects: Queueing theory

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Queueing theory

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
binary trees, data structures, implementation of set operations, mergeable heaps, priority queues