File d'attente prioritaire entière avec deleteMin sensible à la distribution

Existe-t-il dans une file d'attente de priorité entière qui utilise mots d'espace avec les opérations suivantes, le tout dans le pire des cas et sans accès à l'aléatoire:$O(n)$

• createEmptyQueueen pour une constante .$O(lg^c U)$$c$
• insertdans .$O(1)$
• deleteMinen , où \ delta _ {\ min} est la différence entre la clé la plus petite et la deuxième plus petite.$O(\delta_{\min})$$\delta_{\min}$

De plus, une fois qu'une clé $k$ a été soumise à a deleteMin, toutes les autres insertions sont $> k$ .

Travaux connexes:

"Recherches et mises à jour locales rapides dans les univers délimités" de Bose et al., Qui est plus rapide que ce dont j'ai besoin deleteMinmais plus lent que ce dont j'ai besoin insert.

«La pire file d'attente à priorité constante de temps» de Brodnik et al., Qui utilise la «mémoire exotique Yggdrasil». Aux fins de cette question, je suis intéressé par des modèles de RAM entiers plus standard.

Brodnik et Karlsson "Multiprocess Time Queue" , qui limite l'insertion aux éléments avec des clés en $(k_{\min}, k_{\min} + \delta_{\min}]$ , où $k_{\min}$ est la valeur du minimum clé.

Notez que c'est assez simple avec une table de hachage, mais qui utilise l'amortissement et l'aléatoire:

• Les files d'attente sont des paires d'une table de hachage de clés et une copie de la clé minimale.
• insert ajoute la clé à la table de hachage et met à jour la copie de clé minimale, le cas échéant.
• deleteMinrecherche la clé minimale dans la table de hachage, puis recherche la clé minimale suivante en recherchant dans l'ordre.$k_{\min} + 1, k_{\min} +2, k_{\min} + 3, \dots$

Cet article [1] a en outre introduit la propriété "time-finger", une propriété unifiée encapsulant à la fois les propriétés de l'ensemble de travail et de la file d'attente:

Nous présentons une file d'attente prioritaire qui prend en charge les opérations: insérer dans le pire temps constant et supprimer, supprimer-min, trouver-min et diminuer la clé sur un élément dans le pire des cas heure, où (respectivement, ) est le nombre d'éléments auxquels on a accédé après (respectivement, avant) le dernier accès de et qui sont toujours dans la file d'attente prioritaire au moment où l'opération correspondante est effectuée .$x$$O(lg(min\{w_x,q_x\}+2))$$w_x$$q_x$$x$

[1] A. Elmasry, A. Farzan et J. Iacono, «Une propriété unificatrice pour les files d'attente prioritaires sensibles à la distribution», dans Combinatorial Algorithms, vol. 7056, C. Iliopoulos et W. Smyth, Eds. Springer Berlin Heidelberg, 2011, p. 209-222.