Black box for constant-time insertion in priority queues

Stephen Alstrup, Thore Husfeldt, Theis Rauhe, Mikkel Thorup

    Research output: Contribution to journalArticlepeer-review

    10 Citations (SciVal)

    Abstract

    We present a simple black box that takes a priority queue Q which supports find-min, insert, and delete in x-time at most t. Here x-time may be worst-case, expected, or amortized. The black-box transforms Q into a priority queue Q* that supports find-min in constant time, insert in constant x-time, and delete in x-time O(t). Moreover, if Q supports dec-key in constant time, then so does Q*.
    Original languageEnglish
    Pages (from-to)102-106
    JournalACM Transactions on Algorithms
    Volume1
    Issue number1
    DOIs
    Publication statusPublished - 2005

    Subject classification (UKÄ)

    • Computer Science

    Fingerprint

    Dive into the research topics of 'Black box for constant-time insertion in priority queues'. Together they form a unique fingerprint.

    Cite this