Jean Vuillemin
Skip Abstract Section
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.
- 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.Google Scholar
- 2 Aho, A.V., Hopcroft, J.E., and Ullman, J.D. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, Mass., 1974. Google ScholarDigital Library
- 3 Brown, M.R. Implementation and analysis of binomial queue algorithms. (to appear in SICOMP).Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 7 Floyd, R.W. Algorithm 245. Treesort 3. Comm. ACM 7, 12 (Dec. 1964), 701. Google ScholarDigital Library
- 8 Ford, L.R., and Johnson, S.M. A tournament problem. Amer. Math. Monthly 66 (1959), 387-389.Google ScholarCross Ref
- 9 Fran~on, J. Representation d'une file de priorit~s par un arbre binaire. Rapport, Dept. Math., U. de Strasbourg, 1975.Google Scholar
- 10 Gentleman, W.M. Row elimination for solving sparse linear systems and least squares problems. Dundee Biennial Conf. on Numer. Anal., 1975.Google Scholar
- 11 Gormet, G.H. Heaps applied to event driven mechanisms. Comm. ACM 19, 7 (July 1976), 417--418. Google ScholarDigital Library
- 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.Google Scholar
- 13 Johnson, D.B. Algorithms for shortest paths. Ph.D. Th., Cornell U., Ithaca, N.Y., 1973. Google ScholarDigital Library
- 14 Johnson, D.B. Priority queues with update and finding minimum spanning trees. Tech. Rep. 170, Penn. State U., University Park, Pa., 1975.Google ScholarCross Ref
- 15 Jonassen, A., and Dahl, O.J. Analysis of an algorithm for priority queue administration. BIT 15 (1975), 409-422.Google ScholarDigital Library
- 16 Knuth, D.E. The Art of Computer Programming, Vol. 1: Fundamental Algorithms. Addison-Wesley, Reading, Mass., 1968. Google ScholarDigital Library
- 17 Knuth, D.E. The Art of Computer Programming, Vol. 3: Sorting and Searching. Addison-Wesley, Reading, Mass., 1973. Google ScholarDigital Library
- 18 Knuth, D.E. Selected Topics in Computer Science. Lecture Notes Series, Inst. Math. U. of Oslo, 1973. Google ScholarDigital Library
- 19 Malcolm, M.A., and Simpson, R.B. Local versus Global Strategies for Adaptative Quadrature. A CM Trans. Math. Software, 1, 2 (June 1975), 129-146. Google ScholarDigital Library
- 20 Paterson, M., Pippcnger, N., Schfnhage, A. Finding the median. Theory Comp. Rep. no. 6, U. of Warwick, Coventry, England, 1975. Google ScholarDigital Library
- 21 Porter, T., and Simon, I. Random insertion into a priority queue structure. Rep. Stan-Cs-74-460, Dept. Comptr. Sci., Stanford U., Stanford, Calif., 1974. Google ScholarDigital Library
- 22 Prim, R. C. Shortest connection networks and some generalizations. Bell Syst. Tech. J. 36, 6 (1957), 1389-1401.Google ScholarCross Ref
- 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.Google Scholar
- 24 Vaucher, J.G., and Duval, P. A comparison of simulation event list algorithms. Comm. ACM 18, 4 (April 1975), 223-230. Google ScholarDigital Library
- 25 Vuillemin, J. Structures de donndes. Notes de cours de l'ecole d'&6, CEA-EDF-IRIA, 1975.Google Scholar
- 26 Williams, J.W.J. Algorithm 232. Heapsort. Comm. ACM 7, 6 (June 1964), 347-348.Google Scholar
- 27 Wyman, F.P. Improved Event-Scanning Mechanisms for Discrete Event Simulation. Comm. ACM 18, 6 (June 1975), 350-353. Google ScholarDigital Library
Index Terms
- A data structure for manipulating priority queues
Recommendations
(N,n)-preemptive priority queues
In this paper, we propose a new priority discipline, called the (N,n)-preemptive priority discipline. Under this discipline, the preemption of the service of a low-class customer is determined by two thresholds N and n of the queue length of high-class ...
On priority queues with impatient customers
In this paper, we study three different problems where one class of customers is given priority over the other class. In the first problem, a single server receives two classes of customers with general service time requirements and follows a preemptive-...
Priority queues with batch Poisson arrivals
This paper studies batch arrival M^X/G/1 priority queues without and with (multiple or single) vacations. Applying the delay busy cycle analysis, we explicity derive the Laplace-Stieltjes transforms and the first two moments of the waiting time ...
Comments