Black box for constant-time insertion in priority queues
Författare
Summary, in English
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*.
Avdelning/ar
- Computer Science
Publiceringsår
2005
Språk
Engelska
Sidor
102-106
Publikation/Tidskrift/Serie
ACM Transactions on Algorithms
Volym
1
Issue
1
Dokumenttyp
Artikel i tidskrift
Förlag
Association for Computing Machinery (ACM)
Ämne
- Computer Science
Status
Published
ISBN/ISSN/Övrigt
- ISSN: 1549-6333