Black box for constant-time insertion in priority queues
(2005) In ACM Transactions on Algorithms 1(1). p.102-106- 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*.
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/629648
- author
- Alstrup, Stephen ; Husfeldt, Thore LU ; Rauhe, Theis and Thorup, Mikkel
- organization
- publishing date
- 2005
- type
- Contribution to journal
- publication status
- published
- subject
- in
- ACM Transactions on Algorithms
- volume
- 1
- issue
- 1
- pages
- 102 - 106
- publisher
- Association for Computing Machinery (ACM)
- external identifiers
-
- scopus:33846640936
- ISSN
- 1549-6333
- DOI
- 10.1145/1077464.1077471
- language
- English
- LU publication?
- yes
- id
- 11595432-2c98-455a-8d7d-58507e86fa01 (old id 629648)
- date added to LUP
- 2016-04-01 12:15:31
- date last changed
- 2022-04-05 19:49:50
@article{11595432-2c98-455a-8d7d-58507e86fa01, 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*.}}, author = {{Alstrup, Stephen and Husfeldt, Thore and Rauhe, Theis and Thorup, Mikkel}}, issn = {{1549-6333}}, language = {{eng}}, number = {{1}}, pages = {{102--106}}, publisher = {{Association for Computing Machinery (ACM)}}, series = {{ACM Transactions on Algorithms}}, title = {{Black box for constant-time insertion in priority queues}}, url = {{http://dx.doi.org/10.1145/1077464.1077471}}, doi = {{10.1145/1077464.1077471}}, volume = {{1}}, year = {{2005}}, }