Здравствуйте, Беляев Игорь Олегович, Вы писали:
БИО>Данная приоритетная очередь будет использована для разработки агента «хранителя знаний» многоагентной поисковой системы.
А чем
Boost.Heap не устроил?
Здравствуйте, Evgeny.Panasyuk, Вы писали:
EP>Здравствуйте, Беляев Игорь Олегович, Вы писали:
БИО>>Данная приоритетная очередь будет использована для разработки агента «хранителя знаний» многоагентной поисковой системы.
EP>А чем Boost.Heap не устроил?
А просто интересно...
Здравствуйте, Беляев Игорь Олегович, Вы писали:
БИО>В статье представлена реализация приоритетной очереди на основе бинарной, биномиальной и фибоначчиевой куч. Указаны асимптотические сложности и приведены сравнительные характеристики базовых операций.
Особенно обидно за двоичную кучу.
Цитата
Объединение двух бинарных куч
Данную операцию можно выполнить со сложностью O(Nlog(N)), последовательно перебрав все элементы одной кучи за O(N) и добавив их в результирующую за O(log(N)). Низкая производительности данной операции обуславливает необходимость в рассмотрении двух последующих куч.
Это очень грубая оценка. Даже википедия знает, что две двоичные кучи объединяются за время O(N) в худшем случае. Там же есть ссылка, где можно прочитать о том, нужно сделать, чтобы уметь их объединять за время O((logN)
2).
Ну и про низкую производительность, вообще говоря, тоже неправда. На таких малых размерах, как приведены в тестах, низкие накладные расходы двоичной кучи с запасом компенсируют её не самые лучше асимптотические оценки. Только кривая реализация не даёт ей всех обогнать. Это же надо додуматься, использовать std::map внутри реализации двоичной кучи! Эта структура данных на порядок медленнее и сложнее в реализации. О каких тестах производительности тут может идти речь?
