Y at-il une classe de segment de mémoire en C++ qui prend en charge la modification de la priorité des éléments autres que la tête?

Question

J'ai une file d'attente prioritaire d'événements, mais parfois les priorités d'événements changent, donc je voudrais maintenir les itérateurs des demandeurs d'événement dans le tas. Si la priorité change, j'aimerais que le tas soit ajusté en temps de log (n). J'aurai toujours exactement un itérateur pointant vers chaque élément du tas.

Answer 1

Je suis heureux d'annoncer que Boost a maintenant ajouté un Boost.Heap library avec quelques stellar data structures.

L'avantage de ceci est que les tas de Fibonacci supportent la priorité changeante en temps amorti constant.

Malheureusement, tous les tas mutables sont basés sur des nœuds (en d'autres termes, ils ont une indirection supplémentaire comme suggéré par @wilx). @ La réponse de Feruccio aux «mutables heaps» de Boost a du code qui permet d'écrire des tas mutables vectoriels si vous voulez avoir des pointeurs vers des poignées contenues dans votre type de valeur.

Answer 2

Cela ressemble à vous avez besoin de plus d'indirection. Stockez le pointeur vers les événements de la file d'attente de priorité à la place. Lorsque la priorité de certains éléments de la file d'attente change, supprimez-la et réinsérez-la.

Answer 3

Jetez un oeil à mutable heaps de Boost.

Answer 4

Un avertissement est que vous vous retrouvez avec l'événement instable de tri, à savoir l'ordre des événements avec la même priorité est définie (lire «ils seront réorganisés.)