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