Although the methods described here have been used in several recent papers on fast priority queue implementation, this short note brings these results together, along with a description of the authors’ black box transformation and proofs of the complexities of the transformed queue.

The black box replaces the elements of a given priority queue with pointers to linked lists of elements, where the length of each list is limited by a value t representing either the amortized, expected, or worst-case upper bound on find-min, insert, and delete (depending on the desired time complexity measure). Using simple list operations in conjunction with those of the given priority queue, the find-min operation can be implemented in constant time, the insertion operation can be implemented in constant (amortized/expected/worst-case) time, and delete can be implemented in (amortized/expected/worst-case) time O(t). Although some of these results have been achieved in the past, they required assumptions about the relative frequencies of certain operations. No such assumptions are required for the authors’ construction.