Здравствуйте, Беляев Игорь Олегович, Вы писали:

БИО>В статье представлена реализация приоритетной очереди на основе бинарной, биномиальной и фибоначчиевой куч. Указаны асимптотические сложности и приведены сравнительные характеристики базовых операций.

Особенно обидно за двоичную кучу.

Цитата

Объединение двух бинарных куч
Данную операцию можно выполнить со сложностью O(Nlog(N)), последовательно перебрав все элементы одной кучи за O(N) и добавив их в результирующую за O(log(N)). Низкая производительности данной операции обуславливает необходимость в рассмотрении двух последующих куч.

Это очень грубая оценка. Даже википедия знает, что две двоичные кучи объединяются за время O(N) в худшем случае. Там же есть ссылка, где можно прочитать о том, нужно сделать, чтобы уметь их объединять за время O((logN)²).

Ну и про низкую производительность, вообще говоря, тоже неправда. На таких малых размерах, как приведены в тестах, низкие накладные расходы двоичной кучи с запасом компенсируют её не самые лучше асимптотические оценки. Только кривая реализация не даёт ей всех обогнать. Это же надо додуматься, использовать std::map внутри реализации двоичной кучи! Эта структура данных на порядок медленнее и сложнее в реализации. О каких тестах производительности тут может идти речь?

Статья:
Приоритетная очередь на основе бинарной, биномиальной и фибонначиевой куч и ее применение в многоаге

Автор(ы): Беляев Игорь Олегович
Дата: 18.04.2012
В статье представлена реализация приоритетной очереди на основе бинарной, биномиальной и фибоначчиевой куч. Указаны асимптотические сложности и приведены сравнительные характеристики базовых операций. Данная приоритетная очередь будет использована для разработки агента «хранителя знаний» многоагентной поисковой системы.

Авторы:
Беляев Игорь Олегович

Аннотация:
В статье представлена реализация приоритетной очереди на основе бинарной, биномиальной и фибоначчиевой куч. Указаны асимптотические сложности и приведены сравнительные характеристики базовых операций. Данная приоритетная очередь будет использована для разработки агента «хранителя знаний» многоагентной поисковой системы.

Здравствуйте, Беляев Игорь Олегович, Вы писали:

БИО>Данная приоритетная очередь будет использована для разработки агента «хранителя знаний» многоагентной поисковой системы.

А чем Boost.Heap не устроил?

Здравствуйте, Evgeny.Panasyuk, Вы писали:

EP>Здравствуйте, Беляев Игорь Олегович, Вы писали:

БИО>>Данная приоритетная очередь будет использована для разработки агента «хранителя знаний» многоагентной поисковой системы.

EP>А чем Boost.Heap не устроил?
А просто интересно...