Integer priority queue with distribution-sensitive deleteMin

Question

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.

Answer 1

This paper[1] additionally introduced the "time-finger" property, a unified property encapsulating both the working-set and the queueish properties:

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.

[1] A. Elmasry, A. Farzan, and J. Iacono, ‘A Unifying Property for Distribution-Sensitive Priority Queues’, in Combinatorial Algorithms, vol. 7056, C. Iliopoulos and W. Smyth, Eds. Springer Berlin Heidelberg, 2011, pp. 209–222.