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

<blockquote>
  <p>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.</p>
</blockquote>

<p>[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.</p>

CC BY-SA 3.0
2014-06-09T05:03:00.680Z
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
CC BY-SA 3.0
2014-06-10T14:13:36.497Z
Technically it is dependent on those variables; meaning that the deleteMin is distribution sensitive, right?
A T
CC BY-SA 3.0
2014-06-11T00:11:15.390Z
$w_x$ and $q_x$ can vary independently of $\delta_{\textrm{min}}$.
jbapple
CC BY-SA 3.0
2014-06-09T04:58:29.837Z
2014-06-10T14:11:25.303Z
2014-06-10T14:11:25.303Z
A T
<p>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:</p>

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

<p>Furthermore, once a key $k$ has been subject to a <code>deleteMin</code>, all further inserts are $&gt; k$.</p>

<p>Related work:</p>

<p><a href="http://www.cs.umanitoba.ca/~cccg2010/electronicProceedings/paper33.pdf">Bose et al.'s "Fast Local Searches and Updates in Bounded Universes"</a>, which is faster than I need for <code>deleteMin</code> but slower than I need for <code>insert</code>.</p>

<p><a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.28.7131&amp;rep=rep1&amp;type=pdf">Brodnik et al.'s "Worst case constant time priority queue"</a>, which uses the exotic "Yggdrasil memory". For the purposes of this question, I'm interested in more standard integer RAM models.</p>

<p><a href="http://www.imfm.si/preprinti/PDF/00771.pdf">Brodnik and Karlsson's "Multiprocess Time Queue"</a>, which limits insert to elements with keys in $(k_{\min}, k_{\min} + \delta_{\min}]$, where $k_{\min}$ is the value of the minimum key.</p>

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

<ul>
<li>Queues are pairs of a hash table of keys and a copy of the minimum key.</li>
<li><code>insert</code> adds the key to the hash table and updates the minimum key copy if appropriate.</li>
<li><code>deleteMin</code> 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.</li>
</ul>

<ds.data-structures>
Integer priority queue with distribution-sensitive deleteMin
jbapple
# Integer priority queue with distribution-sensitive deleteMin

(Asked by: username_0 on 2013-09-10)

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"](http://www.cs.umanitoba.ca/~cccg2010/electronicProceedings/paper33.pdf), 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"](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.28.7131&rep=rep1&type=pdf), 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"](http://www.imfm.si/preprinti/PDF/00771.pdf), 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.

**Tags:** ds.data-structures

---

## 1 answers

### Answer by username_1 on 2014-06-09. Score: 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.

> **Comments:**
> **username_0**: 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$.  
> **username_1**: Technically it is dependent on those variables; meaning that the deleteMin is distribution sensitive, right?  
> **username_0**: $w_x$ and $q_x$ can vary independently of $\delta_{\textrm{min}}$.  

---

