Queaps

John Iacono, Stefan Langerman

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Abstract

    We present a new priority queue data structure, the queap, that executes insertion in O(1) amortized time and Extract-min in O(log(k + 2)) amortized time if there are k items that have been in the heap longer than the item to be extracted. Thus if the operations on the queap are first-in first-out, as on a queue, each operation will execute in constant time. This idea of trying to make operations on the least recently accessed items fast, which we call the queueish property, is a natural complement to the working set property of certain data structures, such as splay trees and pairing heaps, where operations on the most recently accessed data execute quickly. However, we show that the queueish property is in some sense more difficult than the working set property by demonstrating that it is impossible to create a queueish binary search tree, but that many search data structures can be made almost queueish with a O(log log n) amortized extra cost per operation.

    Original languageEnglish (US)
    Title of host publicationAlgorithms and Computation - 13th International Symposium, ISAAC 2002, Proceedings
    Pages211-218
    Number of pages8
    DOIs
    StatePublished - 2002
    Event13th Annual International Symposium on Algorithms and Computation, ISAAC 2002 - Vancouver, BC, Canada
    Duration: Nov 21 2002Nov 23 2002

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    Volume2518 LNCS
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349

    Other

    Other13th Annual International Symposium on Algorithms and Computation, ISAAC 2002
    CountryCanada
    CityVancouver, BC
    Period11/21/0211/23/02

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Computer Science(all)

    Fingerprint Dive into the research topics of 'Queaps'. Together they form a unique fingerprint.

  • Cite this

    Iacono, J., & Langerman, S. (2002). Queaps. In Algorithms and Computation - 13th International Symposium, ISAAC 2002, Proceedings (pp. 211-218). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2518 LNCS). https://doi.org/10.1007/3-540-36136-7_19