Изменяемая очередь приоритетов, позволяющая увеличить ключ

Question

При реализации алгоритма поиска графа мне требовалась очередь с приоритетами, которая учитывала изменения приоритетов.До сих пор я использовал (detail пространство имен, недокументированное) boost d_ary_heap_indirect, но мне только что сказали, что увеличение приоритетов не определено (что, как я вижу, сейчас упоминается в концепции документация ).

Итак, мне нужно найти структуру, которая позволяет как увеличивать, так и уменьшать.Я уже пробовал просто использовать vector и push_heap / pop_heap / make_heap, но обновления слишком медленные.Какие есть альтернативы?Я вижу, что boost имеет два класса в ожидающих (опять же недокументированных) каталогах, mutable_queue и relaxed_heap, но я могу найти упоминание о них только в пятилетних ветвях рассылки.Каковы различия между ними, и они допускают как увеличение, так и уменьшение?Есть ли реализации, которые не ожидают принятия?

Answer 1

Поместите значение в кучу.Все, что вам нужно сделать, это изменить значение, а затем восстановить инвариант кучи, увеличивая или уменьшая значение.

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

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

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

Answer 2

Библиотека Boost.MultiIndex содержит контейнер, который имеет операции для обновления состояния объекта и соответственно обновит индексы.

В вашем случае функция-член modify выглядитподходить.Из документации:

struct change_name
{
  change_name(const std::string& new_name):new_name(new_name){}

  void operator()(employee& e)
  {
    e.name=new_name;
  }

private:
  std::string new_name;
};

typedef employee_set::index<name>::type employee_set_by_name;
employee_set_by_name& name_index = es.get<name>();

employee_set_by_name::iterator it = name_index.find("Anna Jones");
name_index.modify(it,change_name("Anna Smith"));