A priority queue with the time-finger property

Amr Elmasry, Arash Farzan, John Iacono

    Research output: Contribution to journalArticle

    Abstract

    We present a priority queue that supports insert in worst-case constant time, and delete-min, access-min, delete, and decrease of an element x in worst-case O(log(min{wx,qx})) time, where wx (respectively, qx) is the number of elements that were accessed after (respectively, before) the last access to x and are still in the priority queue at the time when the corresponding operation is performed. (An access to an element is accounted for by any priority-queue operation that involves this element.) Our priority queue then has both the working-set and the queueish properties; and, more strongly, it satisfies these properties in the worst-case sense. From the results in Iacono (2001) [11] and Elmasry et al. (2011) [7], our priority queue also satisfies the static-finger, static-optimality, and unified bounds. Moreover, we modify our priority queue to realize a new unifying property - the time-finger property - which encapsulates both the working-set and the queueish properties.

    Original languageEnglish (US)
    Pages (from-to)206-212
    Number of pages7
    JournalJournal of Discrete Algorithms
    Volume16
    DOIs
    StatePublished - Oct 2012

    Keywords

    • Data structures
    • Distribution-sensitive structures
    • Priority queues
    • Splay trees
    • Working-set bound

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Discrete Mathematics and Combinatorics
    • Computational Theory and Mathematics

    Fingerprint Dive into the research topics of 'A priority queue with the time-finger property'. Together they form a unique fingerprint.

    Cite this