Black box for constant-time insertion in priority queues (note)
Stephen Alstrup, Thore Husfeldt, Theis Rauhe, Mikkel Thorup · ACM Transactions on Algorithms · 2005
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 *.