Heap (по русски называется пирамида) -- интересная стурктура данных, представляемая обычно в виде бинарного дерева и используемая для построения приоритетных очередей, пирамидальной сортировки (также известной, как heapsort) и других алгоритмов, которые работают с графами. Характеиризуется в основном временем вставки и удаления за O(log n).
Основными свойствами (и условиями корректности) пирамиды являются: 1. Полнота -- пирамида представляется в виде дерева, в котором все уровни польностью заполнены кроме, возможно, последнего. 2. Эффективная реализация в виде массива -- так как пирамида (обычно бинарное дерево) обладает полнотой, то реализация такой структуры в виде массива крайне эффективна. 3. Каждый узел в пирамиде либо равен, либо больше сввоих потомков.
Таким образом, пирамида -- эфективная структура данных для тех случаев, когда нужна эффективная вставка элементов в относительно отсортированную структуру данных, а затем получение максимального (или минимального) элемента -- это, кстати, можно считать описанием пирамидальной сортировки.
Удаление из кучи наибольшего (наименьшего) элемента осуществляется в три шага: 1. Удаление корня дерева (получение элемента) 2. Перемещение крайнего нижнего элемента в корень (он является противоположным корню -- наименьшим, если корень наибольший и т.д.), такой элемент в представлении в виде массива обычно оказывается последним. Такой шаг обеспечивает полноту пирамиды. 3. Пошаговое смещение нового корневого элемента вниз по дереву. Тут мы на каждом шаге заменяем наш элемент с наибольшим его потомком, пока он не окажется больше обоих потомков.
