Abstract
A special kind of priority queue structure, priority trees (p-trees), and an algorithm for building such trees are investigated. The main part of the paper is devoted to a mathematical analysis of the algorithm showing that the expected number of key comparisons to insert a “random” element into a “random”p-tree withn nodes isO((logn)2). Also some practical experiments, comparing different types of priority queue strategies, are presented.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Donald E. Knuth,Sorting and Searching, Addison-Wesley 1973.
Ole-Johan Dahl and Dag Belsnes,Algoritmer og datastrukturer, Studentlitteratur 1973.
Jean G. Vaucher and Pierre Duval,A Comparison of Simulation Event List Algorithms, Comm. of the ACM, Vol. 18, no. 4.
Arne Jonassen and Ole-Johan Dahl,Analysis of an Algorithm for Priority Queue Administration, Institute of Mathematics, Univ. of Oslo, 1975.
Arne Jonassen,Additional results from the normal p-tree forest, Institute of Mathematics, Univ. of Oslo, 1975.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Jonassen, A., Dahl, OJ. Analysis of an algorithm for priority queue administration. BIT 15, 409–422 (1975). https://doi.org/10.1007/BF01931680
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF01931680