Skip to main content
Springer Nature Link
Log in

A Priority Queue Transform

  • Conference paper
  • First Online:
Algorithm Engineering (WAE 1999)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 1668))

Included in the following conference series:

  • 902 Accesses

  • 12 Citations

Abstract

A transformation, referred to as depletion, is defined for comparison-based data structures that implement priority queue operations. The depletion transform yields a representation of the data structure as a forest of heap-ordered trees. Under certain circumstances this transform can result in a useful alternative to the original data structure. As an application, we introduce a new variation of skew-heaps that effficiently implements decrease-key operations. Additionally, we construct a new version of the pairing heap data structure that experimentally exhibits improved efficiency.

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

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. M. L. Fredman, On the efficiency of pairing heaps and related data structures, to appear in Journal of the ACM.

    Google Scholar 

  2. M. L. Fredman, R. Sedgewick, D. D. Sleator, and R. E. Tarjan, The pairing heap: a new form of self-adjusting heap, Algorithmica 1,1 (1986), pp. 111–129.

    Article  MathSciNet  Google Scholar 

  3. M. L. Fredman and R. E. Tarjan, Fibonacci heaps and their uses in improved network optimization problems, Journal of the ACM 34,3 (1987), pp. 596–615.

    Article  Google Scholar 

  4. D. W. Jones, An empirical comparison of priority-queue and event-set implementations, Communications of the ACM 29, 4 (1986), pp. 300–311.

    Article  MathSciNet  Google Scholar 

  5. D. D. Sleator and R. E. Tarjan, Self-adjusting heaps. SIAM Journal on Computing 15,1 (1986), pp. 52–69.

    Article  MathSciNet  Google Scholar 

  6. J. T. Stasko and J. S. Vitter, Pairing heaps: experiments and analysis, Communications of the ACM 30,3 (1987), pp. 234–249.

    Article  MathSciNet  Google Scholar 

  7. J. Vuillemin, A data structure for manipulating priority queues, Communications of the ACM 21 (1978) pp. 309–214.

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Rutgers University, New Brunswick, NJ, 08903

    Michael L. Fredman

Authors
  1. Michael L. Fredman
    View author publications

    Search author on:PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Computer Science, Duke University, Box 90129, Durham, NC, 27708-0129, USA

    Jeffrey S. Vitter

  2. Department of Computer Science, University of London, King’s College, Strand, London, WC2R 2LS, UK

    Christos D. Zaroliagis

Rights and permissions

Reprints and permissions

Copyright information

© 1999 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Fredman, M.L. (1999). A Priority Queue Transform. In: Vitter, J.S., Zaroliagis, C.D. (eds) Algorithm Engineering. WAE 1999. Lecture Notes in Computer Science, vol 1668. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48318-7_20

Download citation

  • DOI: https://doi.org/10.1007/3-540-48318-7_20

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-66427-7

  • Online ISBN: 978-3-540-48318-2

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics