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.
Integer priority queue with distribution-sensitive deleteMin
ds.data structures