Я сейчас реализую несколько графовых алгоритмов и хочу контейнер со сложностью кучи Фибоначчи или расслабленной кучи (в частности, я хочу по крайней мере O (logN) для push и pop и O (1) для reduce_key).
Я не заинтересован в том, чтобы реализовать это сам, если это вообще возможно (накладные расходы на разработку и тестирование), и я заметил, что библиотека графов надстроек ссылается на пару вероятных структур данных в ожидающем каталоге. Расслабленная куча в relaxed_heap.hpp выглядит так, но я не могу понять, как ее использовать. Он имеет следующие публичные функции (немного уточнены для ясности):
void push(const value_type& x);
value_type& top();
void pop();
Которые достаточно ясны и реализуют желаемый мне пуш и поп. Дополнительно есть:
void update(const value_type& x);
void remove(const value_type& x);
Я предполагаю, что я могу реализовать редукционный ключ с помощью обновления, но я не понимаю, как. Моя конкретная проблема заключается в том, что я предполагаю, что значение копируется после вызова push. Мне кажется, мне нужен указатель на копию значения в куче, чтобы я мог изменить его по ссылке, а затем вызвать update, чтобы он перетаскивался обратно туда, где он принадлежит. Однако такой указатель, кажется, не доступен?
Кто-нибудь, кто испытал расслабленные кучи в целом или, в частности, развил расслабленные кучи, желает избавить меня от моих страданий объяснением или хорошим фрагментом кода?
Спасибо
Alex