Fila de prioridade inteira com deleteMin sensível à distribuição

Existe em uma fila de prioridade inteira que usa $O(n)$ palavras de espaço com as seguintes operações, todas no pior caso e sem acesso à aleatoriedade:

• createEmptyQueueem $O(lg^c U)$ para alguma constante $c$ .
• insertem $O(1)$ .
• deleteMinem $O(\delta_{\min})$ , onde $\delta_{\min}$ é a diferença entre a menor e a segunda menor chave.

Além disso, uma vez que uma tecla $k$ esteja sujeita a a deleteMin, todas as inserções adicionais serão $> k$ .

Trabalho relatado:

"Pesquisas e atualizações locais rápidas de Boseed Universes" , de Bose et al. , Que é mais rápido do que eu preciso, deleteMinmas mais lento do que eu preciso insert.

Brodnik et al., "Pior fila de prioridade de tempo constante" , que usa a exótica "memória Yggdrasil". Para os fins desta pergunta, estou interessado em mais modelos de RAM inteira padrão.

"Fila de tempo de multiprocesso" de Brodnik e Karlsson , que limita a inserção a elementos com chaves em $(k_{\min}, k_{\min} + \delta_{\min}]$ , onde $k_{\min}$ é o valor mínimo chave.

Observe que isso é bastante simples com uma tabela de hash, mas que usa amortização e aleatoriedade:

• Filas são pares de uma tabela de chaves hash e uma cópia da chave mínima.
• insert adiciona a chave à tabela de hash e atualiza a cópia mínima da chave, se apropriado.
• deleteMinprocura a chave mínima na tabela de hash e procura a próxima chave mínima pesquisando em ordem.$k_{\min} + 1, k_{\min} +2, k_{\min} + 3, \dots$

Este artigo [1] introduziu adicionalmente a propriedade "time-finger", uma propriedade unificada que encapsula as propriedades do conjunto de trabalho e da fila:

Apresentamos uma fila de prioridade que suporta as operações: insira no pior dos casos, tempo constante e exclua, apague-min, encontre-min e tecla de diminuição em um elemento no pior caso time, em que (respectivamente, ) é o número de elementos que foram acessados ​​após (respectivamente, antes) o último acesso de e ainda estão na fila de prioridade no momento em que a operação correspondente é executada .$x$$O(lg(min\{w_x,q_x\}+2))$$w_x$$q_x$$x$

[1] A. Elmasry, A. Farzan e J. Iacono, 'Uma propriedade unificadora para filas de prioridade sensível à distribuição', em Combinatorial Algorithms, vol. 7056, C. Iliopoulos e W. Smyth, Eds. Springer Berlin Heidelberg, 2011, pp. 209–222.