Queaps

John Iacono, Stefan Langerman

    Research output: Contribution to journalArticlepeer-review

    Abstract

    A new priority queue structure, the queap, is introduced. The queap 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 logn) amortized extra cost per operation.

    Original languageEnglish (US)
    Pages (from-to)49-56
    Number of pages8
    JournalAlgorithmica (New York)
    Volume42
    Issue number1
    DOIs
    StatePublished - Mar 2005

    Keywords

    • Data structures

    ASJC Scopus subject areas

    • Computer Science(all)
    • Computer Science Applications
    • Applied Mathematics

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

    Cite this