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

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

Т.е. эта статья в рамках какой-нибудь кандидатской-диплома-етс, и по формальным причинам Вам нужно это упомянуть.
Идея понятна. Нельзя ли это как-нибудь вынести за пределы статьи? Или минимизировать вступление. Примерно так:

— достаточно общё сформулировать задачу, решаемую приоритетными очередями
— уточнить, что в частности их можно использовать для хранения документов и получения списка наиболее релевантных.

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

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

Я имел ввиду, что id используются только в операции change. Если в конкретной ситуации нам не нужна эта операция, можно было бы без них обойтись.

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

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

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

Не совсем понял, как.
Берём элемент, меняем его с последним, после чего выкидываем.
После чего применяем к бывшему последнему, оказавшемуся в неправильном месте, алгоритм для "просеивания вниз".
Где подвох? Можете привести пример, на котором этот вариант ломается?

Кстати, если всё так, как Вы говорите, возможно, стоит добавить пример в статью, т.к. подобная "оптимизация" приходит в голову моментально, если она что-то рушит, стоит это показать.

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

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

Честно говоря не помню уже Видимо, два месяца назад у меня была какая-то мысль, как сделать это оптимальнее. Сейчас не могу сказать.

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

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

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

Скачал, постараюсь сегодня посмотреть.