Advanced

Black box for constant-time insertion in priority queues

Alstrup, Stephen; Husfeldt, Thore LU ; Rauhe, Theis and Thorup, Mikkel (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:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
in
ACM Transactions on Algorithms
volume
1
issue
1
pages
102 - 106
publisher
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
2007-11-27 13:17:52
date last changed
2017-10-01 03:51:02
@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    = {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},
  volume       = {1},
  year         = {2005},
}