Skip to main content

Advertisement

Springer Nature Link
Log in

Design and implementation of an efficient priority queue

  • Published:
Mathematical systems theory Aims and scope Submit manuscript

Abstract

See More

We present a data structure, based upon a hierarchically decomposed tree, which enables us to manipulate on-line a priority queue whose priorities are selected from the interval 1,⋯,n with a worst case processing time of\(\mathcal{O}\) (log logn) per instruction. The structure can be used to obtain a mergeable heap whose time requirements are about as good. Full details are explained based upon an implementation of the structure in a PASCAL program contained in the paper.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles and news from researchers in related subjects, suggested using machine learning.

References

  1. Aho, A. V., J. E. Hopcroft andJ. D. Ullman,The design and analysis of computer Algorithms, Addison Wesley, Reading, Mass. (1974).

    Google Scholar 

  2. Aho, A. V., J. E. Hopcroft andJ. D. Ullman,On finding lowest common ancestors in tress, Proc. 5-th ACM symp. Theory of Computing (1973), 253–265.

  3. Emde Boas, P. Van,An O (n log log n) On-Line Algorithm for the Insert-Extract Min Problem, Rep. TR 74-221 Dept. of Comp. Sci., Cornell Univ., Ithaca 14853, N.Y. Dec. 1974.

    Google Scholar 

  4. Even, S. andO. Kariv,Oral Commun., Berkeley, October 1975.

  5. Fischer, M. J.,Efficiency of equivalence algorithms, in: R. E. Miller andJ. W. Thatcher (eds.),Complexity of Computer Computations, Plenum Press, New York (1972), 158–168.

    Google Scholar 

  6. Hopcroft, J. andJ. D. Ullman,Set-merging Algorithms, SIAM J. Comput. 2 (Dec. 1973), 294–303.

    Google Scholar 

  7. Hunt, J. W. andT. G. Szymanski,A fast algorithm for computing longest common subsequences. Manuscript. Dept. Electr. Eng. Princeton Univ. Princeton, N.J. 08540. Oct. 1975.

    Google Scholar 

  8. Tarjan, R. E.,Applications of path compression on balanced trees. Manuscript. Stanford Oct. 75. (Submitted toJACM).

  9. Tarjan, R. E.,Efficiency of a good but non linear set union algorithm,J. Assoc. Comput. Mach. 22 (1975), 215–224.

    Google Scholar 

  10. Tarjan, R. E.,Edge disjoint spanning trees, dominators and depth first search, Rep. CS-74-455 (Sept. 1974), Stanford.

  11. Wirth, N.,The Programming Language PASCAL (revised report), in K. Jensen and N. WirthPASCAL User Manual and Report, Lecture Notes in Computer Science 18, Springer, Berlin (1974).

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Mathematical Centre, 2e Boerhaavestraat 49, Amsterdam, Netherlands

    P. van Emde Boas & R. Kaas

  2. Mathematical Institute, University of Amsterdam, Roeterstraat 15, Amsterdam, The Netherlands

    E. Zijlstra

Authors
  1. P. van Emde Boas
    View author publications

    You can also search for this author inPubMed Google Scholar

  2. R. Kaas
    View author publications

    You can also search for this author inPubMed Google Scholar

  3. E. Zijlstra
    View author publications

    You can also search for this author inPubMed Google Scholar

Additional information

Work supported by grant CR 62-50. Netherlands Organization for the Advancement of Pure Research (Z.W.O.).

Rights and permissions

Reprints and permissions

About this article

Cite this article

van Emde Boas, P., Kaas, R. & Zijlstra, E. Design and implementation of an efficient priority queue. Math. Systems Theory 10, 99–127 (1976). https://doi.org/10.1007/BF01683268

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01683268

Keywords