Есть ли в C ++ класс кучи, который поддерживает изменение приоритета элементов, отличных от заголовка?

Question

У меня есть приоритетная очередь событий, но иногда приоритеты событий меняются, поэтому я бы хотел сохранить итераторы из инициаторов событий в куче. Если приоритет изменится, я бы хотел, чтобы куча корректировалась за время log (n). У меня всегда будет ровно один итератор, указывающий на каждый элемент в куче.

Answer 1

Взгляните на изменчивые кучи Boost .

Answer 2

Я рад сообщить, что Boost теперь добавил библиотеку Boost.Heap с некоторыми звездными структурами данных .

Преимущество этого состоит в том, что кучи Фибоначчи поддерживают изменение приоритета в постоянное время амортизации.

К сожалению, все изменяемые кучи основаны на узлах (другими словами, они имеют дополнительное косвенное указание, как предполагает @wilx). @ Ответ Феруччио на «изменяемые кучи» Буста содержит код, позволяющий писать изменяемые кучи на векторной основе, если вы хотите иметь указатели на дескрипторы, содержащиеся в вашем типе значения.

Answer 3

Звучит так, будто вам нужно больше косвенности. Вместо этого сохраните указатель на события в приоритетной очереди. При изменении приоритета какого-либо элемента очереди удалите его и вставьте заново.

Answer 4

Предупреждение здесь заключается в том, что в результате вы получаете нестабильную сортировку событий, то есть упорядочение событий с одинаковым приоритетом не определено (читайте «они будут переупорядочены».)