Cola de prioridad entera con deleteMin sensible a la distribución

¿Existe una cola de prioridad entera que usa palabras de espacio con las siguientes operaciones, todo en el peor de los casos y sin acceso a aleatoriedad:$O(n)$

• createEmptyQueueen para alguna constante c .$O(lg^c U)$$c$
• inserten .$O(1)$
• deleteMinen , donde δ min es la diferencia entre la clave más pequeña y la segunda clave más pequeña.$O(\delta_{\min})$$\delta_{\min}$

Además, una vez que una clave ha sido sujeta a a , todas las inserciones adicionales son > k .$k$deleteMin$> k$

Trabajo relacionado:

Bose et al., "Búsquedas locales rápidas y actualizaciones en universos limitados" , que es más rápido de lo que necesito deleteMinpero más lento de lo que necesito insert.

La "cola de prioridad de tiempo constante" en el peor de los casos de Brodnik et al. , Que utiliza la exótica "memoria Yggdrasil". A los fines de esta pregunta, me interesan más modelos de RAM enteros estándar.

La "Cola de tiempo multiproceso" de Brodnik y Karlsson , que limita la inserción a elementos con claves en , donde k min es el valor de la clave mínima.$(k_{\min}, k_{\min} + \delta_{\min}]$$k_{\min}$

Tenga en cuenta que esto es bastante simple con una tabla hash, pero que usa amortización y aleatoriedad:

• Las colas son pares de una tabla hash de claves y una copia de la clave mínima.
• insert agrega la clave a la tabla hash y actualiza la copia mínima de la clave si corresponde.
• deleteMin$k_{\min} + 1, k_{\min} +2, k_{\min} + 3, \dots$

Este documento [1] introdujo adicionalmente la propiedad "time-finger", una propiedad unificada que encapsula tanto el conjunto de trabajo como las propiedades de la cola:

$x$$O(lg(min\{w_x,q_x\}+2))$$w_x$$q_x$$x$

[1] A. Elmasry, A. Farzan y J. Iacono, 'Una propiedad unificadora para colas de prioridad sensibles a la distribución', en Algoritmos combinatorios, vol. 7056, C. Iliopoulos y W. Smyth, Eds. Springer Berlin Heidelberg, 2011, págs. 209–222.