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

SH>Здравствуйте, Kupaev, Вы писали:

K>>Беляев Игорь Олегович
K>>Приоритетная очередь на основе бинарной, биномиальной и фибонначиевой куч и ее применение в многоагентных поисковых системах

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

K>>Код к статье

SH>О! Когда-то хотел написать про это статью, но заленился Спасибо, что взяли на себя.

SH>Зачем нужна вся история с многоагентным поиском? Она появляется только во введении и нигде дальше не используется (и это замечательно). Мне кажется всё это можно выбросить и посвятить статью просто приоритетным очередям на основе куч. Которые можно использовать не только в поиске но и в какой-нибудь в обработке запросов (ну или где ещё нужны приоритетные очереди). Тема отличная, и совсем не обязательно хвастаться, что вы знаете, что такое tf-idf и ещё много умных слов, не имеющих отношения к делу

Если бы изначально была задача написать статью про приоритетные очереди, то конечно бы не было этого утомительного введения про многоагентный поиск. Мне нужно было показать использование различных видов приоритетных очередей конкретно в информационном поиске на примере конкретной задачи. Собственно сама задача была описана только во введении. А дальше описывается обобщенная реализация приоритетной очереди вне зависимости от предметной области. И в конце демонстрационный пример также имеет обобщенный характер.

SH>По С-шному интерфейсу, лучше так:

SH>bool empty() --> bool empty() const
SH>int size() --> int size() const (size_t size() const)
SH>int push(T obj) --> int push(const T& obj)
SH>T top() --> const T& top() const
SH>bool change(int id, T new_obj) --> bool change(int id, const T& new_obj)

SH>Лишние константы не помешают, а лишних копирований стоит избегать (на случай если T вдруг окажется не int-ом).
Согласен.

SH>Идея с id-шниками в общей реализации кажется мне сомнительной. Она нужна только когда нужна, а тормозить будет всегда. Может быть сделать отдельную реализацию?
Идея с id-шниками появилась и реализовывалась только из-за того, что разные кучи имеют различную внутреннюю организацию, и только для того, чтобы приоритетная очередь вне зависимости от внутренней кучи имела один и тот же интерфейс.

>>> В литературе обычно умалчивается информация об авторе данной структуры данных,

SH>Скрывают!
SH>Умалчивание это сознательное сокрытие известной информации.
SH>Думаю, что этот смысл тут не подходит, а значит и слово нужно другое.

>>> Рисунок 2. Хранение кучи в виде массива. Верхний ряд – индекс элемента, нижний – числовое значение

SH>Даже при том, что я знаю, как устроена бинарная куча, c первого взгляда я ничего не понял. Вот эти синие -- это от кого куда? Почему только по одной, детей же двое? Синие сверху и синие снизу как-то связаны?

SH>Со второго взгляда, прикинув, как должно быть, я понял, что сверху одна половина, а снизу другая. Но в общем картинка неудачна, ничего не проясняет.
Возможно рисунок не самый удачный.

>>> При этом может произойти нарушения целостности кучи (см. п. 2).

SH>Я бы не называл это целостностью... Или это устоявшееся словоприменение?
Скорее устоявшееся. Если вам известно другое определение этого понятия, пожалуйста поделитесь.


>>> Т.к. дерево является бинарным, то сложность данной операции O(log(N)).

SH>Я бы ещё отметил, что это не просто бинарное дерево, а это всегда идеально сбалансированное бинарное дерево. Именно поэтому гарантируется O(log(N))
Полностью согласен.

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

SH>??

SH>Почему нельзя просто поменять местами с последним, т.е. удалить по тому же алгоритму, что и корневой?
Если просто поменять местами с последним, то может возникнуть ситуация, при которой целостность кучи будет нарушена двумя элементами. А представленные алгоритмы могут восстановить целостность кучи только если она нарушена не более одним элементом.



>>> Учитывая возможности современного компьютера и адекватных потребностей при использовании биномиальной кучи можно ограничить общее количество элементов в ней до 231-1.

SH>Что-то не так с русским языком.
Согласен.

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

SH>Здесь это хотя бы осмысленно, хотя тоже не оптимально.
Идея та же самая, что и в прошлый раз. Что подразумевается под оптимальным способом?

>>> Рисунок 9. Пример корректного фибоначчиева дерева.

SH>Много стрелочек, которые на рисунке выглядят одинаково, а на самом деле принципиально отличаются. Три типа:
SH>- ссылка на ребёнка
SH>- ссылка на родителя
SH>- ссылки между братьями

SH>Может их как-то различать? Или хотя бы убрать ссылки на родителей?
Если стрелки разукрашивать, то получится слишком ярко. Если убрать ссылки на родителя, то может потеряться понимание общей организации кучи.


>>> Но, тем не менее, амортизированная сложность ее O(logN)[6].

SH>Что такое "амортизированная сложность"? Я легко могу не знать этого термина, это нормально. Средняя ожидаемая сложность?
Гарантируется средняя производительность операций в наишудшем случае.

>>> Демонстрационный проект

SH>А можно вместо Дейкстры приложить код, который позволяет посчитать статистику? Меня честно говоря удивила бинарная куча, я думал хотя бы в первом тесте она будет достаточно хороша. А вот втором по идее, она должна отставать более чем линейно из-за долгих объединений, разве нет? В общем, что-то меня смущают полученные результаты. Кстати, а что там на осях, секунды и количество элементов? Надо бы упомянуть где-нибудь.

Проект для подсчета статистики: http://goo.gl/FLxlR (подцепляйте нужные файлы: test_speed_0.cpp или test_speed_1.cpp)
Бинарная куча в первом тесте проигрывает из-за того, что высота поддерева, в котором происходит просейка вверх/вниз всегда будет больше, чем у биномиальной или фибоначчиевой кучи.
По поводу второго теста вы правы, там отставание не линейное, а квазилинейное, т.к. сложность объединения O(N*logN).

На осях секунды и количество элементов. Проглядел. Спасибо, что заметили.