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

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

S>Здесь я не прав. Нет подвоха, все будет работать так, как Вы написали.

Ну, только иногда надо будет запускать просеивание не вниз, а вверх. Если бывший нижний узел окажется не в "своей" ветке дерева, он может оказаться и меньше.

По поводу тестов.

Во-первых, VC++ очень добрый компилятор, если такое пропускает Для gcc мне пришлось немного допилить шаблоны.

binary_heap(bool (*cmp) (const T&, const T&)) {} : base_heap(cmp)

не работает, он не знает, что такое base_heap. Правильно base_heap<T, int>. Ещё правильнее

    typedef base_heap<T, int> base;
    ...
    binary_heap(bool (*cmp) (const T&, const T&)) : base(cmp) {}

Дальше, он не знает что такое id_by_node, node_by_id и get_next_id. Вот тут объяснено, почему и не должен знать: http://rsdn.ru/forum/cpp/374683.flat.aspx

Автор: Дмитрий Наумов
Дата: 04.09.03

(см. в теме и по ссылкам в ответе Павла Кузнецова)
Решается при помощи this->get_next_i() и using base::node_by_id.

Аналогично с остальными двумя кучами.

Во-вторых, Ваши результаты у меня подтвердились и даже время примерно то же (я только test_speed_0 запускал).

В-третьих, я поставил эксперимент. Убрал наследование от base_head, все id-шники и заменил _less на <.

Бинарная куча всех сделала Хотя тут результаты очень близкие, она только немного быстрее биномиальной. По соотношениям с исходной версией -- биномиальная ускорилась примерно в 5 раз. И наибольшую роль тут играют именно id-шники. _less компилятор подставляет довольно эффективно, вызовы виртуальных функций тоже, видимо, не производит, вызывает напрямую, а вот с этими картами возиться приходится (я проверял, как меняется скорость, если оставить base_heap, но убрать из _swap перестановку в картах и из push/pop добавление/удаление связей). Вот примерно так операции change и remove влияют на общую производительность кучи.

В-четвёртых, чтобы делать подробные замечания по коду мне надо разобраться в нём глубже, не уверен, что буду это делать. Но вот функции check_XXX_heap и XXXX_0 из модуля test_speed_0.cpp просто так и просятся на то, чтобы сделать их шаблонными и передавать тип кучи в параметре.

По поводу введения. Если я прав, и статья для диплома/кандидатской, наверное, у Вас есть научный руководитель? Обсудите с ним, может это можно сделать как-то изящнее. Просто я вспомнил анекдот Про студента, который перед экзаменом по зоологии выучил только про блох, и отвечал примерно так "медведь это такой большой зверь, у него есть четыре лапы, голова и хвост. Он весь покрытый шерстью. В шерсти медведя водятся блохи. Так вот о блохах ..." В текущем виде статья построена по такой же модели. Мне кажется, должен быть лучший вариант.