John Iacono, Stefan Langerman

    Research output: Contribution to journalArticlepeer-review


    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)
    Issue number1
    StatePublished - Mar 2005


    • Data structures

    ASJC Scopus subject areas

    • General Computer Science
    • Computer Science Applications
    • Applied Mathematics


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

    Cite this