mayton
1) Интересует где и как применяется. По моим сведениям
на базе heap построены такие структуры как очереди с приоритетами
(PriorityQueue).


В С++/stl есть методы для превращения векторов в пирамиду
(пирамидизация) и получение max/min ключа std::make_heap(..),
pop_heap(..) e.t.c.

Пирамидальная сортировка использует пирамиду как 1-ю фазу
сортировки. (См. линк).

Вобщем - поделитесь инфой кто где применял.


Данная структура используется для сортировки за и для реализации priority queue. Применяется, например, в жадных алгоритмах, в задачах планирования(возможно даже в банальном tfs, но в этом я не уверен).

mayton2) Интересует сравнение с Set/TreeSet/(Black&Red tree)
особенно в части тех-же очередей. Скользящее максимальное.

Условия тестинга. Как?

Что такое скользящее максимальное?
mayton3) Прочие опции . Что еще можно получить с пирамиды?
Какова будет стоимость операций update ключа. Или удаления
элемента с середины пирамиды? Алгоритмически - заявлены
только - добавление в хвост и взятие головы (min/max).
А как быть с прочими операциями search?


При создании пирамиды элементы двигаются пузырьком, т.к. высота двоичной пирамиды , то и двигаться пузырек может не больше этого расстояния, потому асимптотика вставки
Search? Данная структура данных, по крайней мере двоичная пирамида не предназначена для поиска, поскольку мы можем наблюдать только слабую упорядоченность - min heap или max heap. Потому поиск элемента занимает линейное время


mayton4) Space Utilization . Вобщем если сравнивать с красно-черным
деревом - то привлекательна экономия места. В пирамидке нет
кросс-ссылок на элементы и можно всю структуру уложить в вектор.

Можно, это одна из особенностей пирамиды)


mayton6) Сравнение heap-sort с QuickSort (by Tony Hoare). . Чуть
позже я приведу скриншот из книжки маэстро Вирта. Обсудим.

Худшее время сортировки с использованием пирамиды , qsort - . Мне кажется, это самое важное различие. Скорее всего в каких либо ОСРВ используются именно такие алгоритмы, но это только мое предположение))

д0kХДля меня, как программера ушедшего в сисадминство и дба,
куча ( heap) асоциируется с возможностью выгрузки в своп
или возможности использования дисковго пространства ( temp space) непосредственно
в алгоритме сортировки.


Вы имеете ввиду отсутствие дополнительных затрат по памяти при сортировке кучей?