J'utilise une file d'attente prioritaire qui base initialement la priorité de ses éléments sur une heuristique. Au fur et à mesure que les éléments sont retirés de la file, l'heuristique est mise à jour et les éléments actuellement dans la file peuvent voir leur clé augmentée.
Je sais qu'il y a des tas (les tas de Fibonacci en particulier) qui ont amorti O(1) les opérations sur les clés de diminution, mais y a-t-il des structures de tas qui ont des limites similaires sur les opérations sur les clés d'augmentation ?
Pour mon application, il ne s'agit pas d'un problème de performance (un tas binaire fonctionne bien), mais d'une simple curiosité académique.
Edit : pour clarifier, je recherche une structure de données qui a un temps plus rapide que O(logn) pour le touche d'augmentation l'opération, pas la touche de diminution. Mon application ne diminue jamais la clé car l'heuristique surestime la priorité.
