A Unifying Property for Distribution-Sensitive Priority Queues

We present a priority queue that supports the operations:

insert

in worst-case constant time, and

delete

,

delete-min

,

find-min

and

decrease-key

on an element

x

in worst-case

$O(\lg(\min\{w_x, q_x\}+2))$

time, where

w

x

(respectively,

q

x

) is the number of elements that were accessed after (respectively, before) the last access of

x

and are still in the priority queue at the time when the corresponding operation is performed. Our priority queue then has both the working-set and the queueish properties; and, more strongly, it satisfies these properties in the worst-case sense. We also argue that these bounds are the best possible with respect to the considered measures. Moreover, we modify our priority queue to satisfy a new unifying property — the time-finger property — which encapsulates both the working-set and the queueish properties.

In addition, we prove that the working-set bound is asymptotically equivalent to the unified bound (which is the minimum per operation among the static-finger, static-optimality, and working-set bounds). This latter result is of tremendous interest by itself as it had gone unnoticed since the introduction of such bounds by Sleater and Tarjan [10].

Together, these results indicate that our priority queue also satisfies the static-finger, the static-optimality and the unified bounds.