# Integer priority queue with distribution-sensitive deleteMin

Is there in an integer priority queue that uses $O(n)$ words of space with the following operations, all in worst-case time and without access to randomness:

• createEmptyQueue in $O(lg^c U)$ for some constant $c$.
• insert in $O(1)$.
• deleteMin in $O(\delta_{\min})$, where $\delta_{\min}$ is the difference between the smallest and the second-smallest key.

Furthermore, once a key $k$ has been subject to a deleteMin, all further inserts are $> k$.

Related work:

Bose et al.'s "Fast Local Searches and Updates in Bounded Universes", which is faster than I need for deleteMin but slower than I need for insert.

Brodnik et al.'s "Worst case constant time priority queue", which uses the exotic "Yggdrasil memory". For the purposes of this question, I'm interested in more standard integer RAM models.

Brodnik and Karlsson's "Multiprocess Time Queue", which limits insert to elements with keys in $(k_{\min}, k_{\min} + \delta_{\min}]$, where $k_{\min}$ is the value of the minimum key.

Note that this is pretty simple with a hash table, but that uses amortization and randomness:

• Queues are pairs of a hash table of keys and a copy of the minimum key.
• insert adds the key to the hash table and updates the minimum key copy if appropriate.
• deleteMin looks up the minimum key in the hash table, then searches for the next minimum key by searching for $k_{\min} + 1, k_{\min} +2, k_{\min} + 3, \dots$ in order.

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.
• This does not answer the question. I am asking for operations that take time proportional to the distance from the smallest to the second smallest key. This measure is incomparable with a measure based $w_x$ and $q_x$. – jbapple Jun 9 '14 at 5:03
• $w_x$ and $q_x$ can vary independently of $\delta_{\textrm{min}}$. – jbapple Jun 11 '14 at 0:11