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

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

Ответы

Ответ 1

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

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

К сожалению, все изменчивые кучи node (другими словами, они имеют дополнительную косвенность, как было предложено @wilx). @Feruccio ответ Boost "mutable heaps" имеет код, который позволяет писать векторные мутируемые кучи, если вы хотите иметь указатели на дескрипторы, содержащиеся в вашем типе значений.

Ответ 3

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

Ответ 4

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