A unifying property for distribution-sensitive priority queues

Amr Elmasry, Arash Farzan, John Iacono

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

    Abstract

    We present a priority queue that supports the operations: insert in worst-case constant time, and delete, delete-min, find-min and decrease-key on an element x in worst-case O(lg(min{wx, qx} + 2)) time, where wx (respectively, qx) is the number of elements that were accessed after (respectively, before) the last access of x and are still in the priority queue at the time when the corresponding operation is performed. 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. We also argue that these bounds are the best possible with respect to the considered measures. Moreover, we modify our priority queue to satisfy a new unifying property - the time-finger property - which encapsulates both the working-set and the queueish properties. In addition, we prove that the working-set bound is asymptotically equivalent to the unified bound (which is the minimum per operation among the static-finger, static-optimality, and working-set bounds). This latter result is of tremendous interest by itself as it had gone unnoticed since the introduction of such bounds by Sleater and Tarjan [10]. Together, these results indicate that our priority queue also satisfies the static-finger, the static-optimality and the unified bounds.

    Original languageEnglish (US)
    Title of host publicationCombinatorial Algorithms - 22nd International Workshop, IWOCA 2011, Revised Selected Papers
    Pages209-222
    Number of pages14
    DOIs
    StatePublished - 2011
    Event22nd International Workshop on Combinatorial Algorithms, IWOCA 2011 - Vancouver, BC, Canada
    Duration: Jul 20 2011Jul 22 2011

    Publication series

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

    Other

    Other22nd International Workshop on Combinatorial Algorithms, IWOCA 2011
    CountryCanada
    CityVancouver, BC
    Period7/20/117/22/11

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Computer Science(all)

    Fingerprint Dive into the research topics of 'A unifying property for distribution-sensitive priority queues'. Together they form a unique fingerprint.

  • Cite this

    Elmasry, A., Farzan, A., & Iacono, J. (2011). A unifying property for distribution-sensitive priority queues. In Combinatorial Algorithms - 22nd International Workshop, IWOCA 2011, Revised Selected Papers (pp. 209-222). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7056 LNCS). https://doi.org/10.1007/978-3-642-25011-8_17