Bonjour a vous tous,

J'ai une question d'algo pour vous aujourd'hui. Je suis a la recherche d'une structure de donnee pour implementer une file de priorite qui supporte ces operations:
extract-min en O(log n)
peek-min en O(1) amorti
increase-key en O(1) amorti

Notez bien que je cherche extract-min et increase-key. Je ne suis pas interesse par decrease-key. Les tas de fibonnacci supportent extract-min en O(log n) et decrease-key en O(1), mais ils ne supportent pas increase-key. Si on retourne la structure pour avoir increase-key, alors on a extract-max mais pas extract-min.

Connaissez vous une structure de donnees qui supporte extract-min et increase-key de facon efficace?

ca va faire du increase-key en O(log n) un truc comme ca, pas en O(1). non?

J'ai regarde des politique de tas avec reconstruction du tas juste quand on a besoin, mais au pire ca, ca degrade a O(log n) amorti.

C'est un truc plus intelligent que ca qu'il faut. Certainement une construction a la fibonacci heap, mais je en connais pas cette structure assez pour voir comment la modifier.

Maintenir l'integrite de la structure n'est en effet pas tres difficile, mais je ne suis pas sur que tu conserve la garantie asymptotique de la structure. L'analyse m'echappe un peu. Il faudrait vraiment que je regarde cette structure proprement un jour.