Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

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
; ; and
organization
publishing date
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}},
}