Black box for constant-time insertion in priority queues

Forskningsoutput: TidskriftsbidragArtikel i vetenskaplig tidskrift

Standard

Black box for constant-time insertion in priority queues. / Alstrup, Stephen; Husfeldt, Thore; Rauhe, Theis; Thorup, Mikkel.

I: ACM Transactions on Algorithms, Vol. 1, Nr. 1, 2005, s. 102-106.

Forskningsoutput: TidskriftsbidragArtikel i vetenskaplig tidskrift

Harvard

APA

CBE

MLA

Vancouver

Author

Alstrup, Stephen ; Husfeldt, Thore ; Rauhe, Theis ; Thorup, Mikkel. / Black box for constant-time insertion in priority queues. I: ACM Transactions on Algorithms. 2005 ; Vol. 1, Nr. 1. s. 102-106.

RIS

TY - JOUR

T1 - Black box for constant-time insertion in priority queues

AU - Alstrup, Stephen

AU - Husfeldt, Thore

AU - Rauhe, Theis

AU - Thorup, Mikkel

PY - 2005

Y1 - 2005

N2 - 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*.

AB - 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*.

U2 - 10.1145/1077464.1077471

DO - 10.1145/1077464.1077471

M3 - Article

VL - 1

SP - 102

EP - 106

JO - ACM Transactions on Algorithms

T2 - ACM Transactions on Algorithms

JF - ACM Transactions on Algorithms

SN - 1549-6333

IS - 1

ER -