Black box for constant-time insertion in priority queues

Forskningsoutput: TidskriftsbidragArtikel i vetenskaplig tidskrift


title = "Black box for constant-time insertion in priority queues",
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 = "Stephen Alstrup and Thore Husfeldt and Theis Rauhe and Mikkel Thorup",
year = "2005",
doi = "10.1145/1077464.1077471",
language = "English",
volume = "1",
pages = "102--106",
journal = "ACM Transactions on Algorithms",
issn = "1549-6333",
publisher = "ACM",
number = "1",