Пирамиды и пирамидальная сортировка

Пирамида
Пирамида является структурой данных, позволяющей обратиться к наибольшему элементу за время O(1), а также позволяющая удалять наибольший элемент и вставлять новый элемент за время O(log2N).
Пирамида – это разновидность двоичного дерева, обладающего двумя свойствами. Первое свойство заключается в том, что любой узел такого дерева больше либо равен любого из своих потомков.
Это свойство называется свойством слабой упорядоченности.

Пример пирамиды

Свойство полноты
Второе свойство называется свойством полноты и заключается в том, что это дерево содержит все возможные узлы при заполнении слева направо и сверху вниз.
На рисунке слева изображено полное дерево, а справа – неполное.

Пирамида на основе массива
Наиболее простой реализацией пирамиды является реализация на основе массива.
При этом каждому узлу дерева соответствует конкретная ячейка массива.
Именно свойство полноты позволяет осуществить такое отображение (обеспечить отсутствие «дыр» в массиве).

Пример пирамиды на основе массива

Связь между деревом и массивом
Благодаря такому отображению для любого узла можно определить индексы его родителя и потомков. Пусть i – индекс некоторого узла в массиве, тогда
индекс родителя равен (i-1) /2;
индекс левого потомка равен 2*i+1;
индекс левого потомка равен 2*i+2.
В качестве упражнения проверьте эти формулы для приведённого рисунка.

Реализация операций
Рассмотрим теперь, как реализуются операции взятия наибольшего элемента, вставки нового элемента и удаления наибольшего.
Для обращения к наибольшему элементу пирамиды достаточно взять первый элемент массива.
Операции вставки нового элемента и удаления наибольшего элемента несколько сложнее, то осуществляются быстро – за время O(log2N).

Удаление вершины
Поскольку удаляется первый элемент, то в массиве образуется «дыра», и возникает необходимость исключить её, восстановив тем самым полноту дерева. Для этого существует следующий алгоритм:
переместить последний узел в корень (на место удалённого);
смещать его вниз до тех пор, пока он не окажется на подходящем месте (меньше либо равен родители и больше либо равен потомков).
При смещении вниз, очевидно, существуют две альтернативы: влево или вправо. Так вот смещать следует в сторону большего из этих двух узлов, чтобы не нарушить слабую упорядоченность.

Пример удаления вершины

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

Пример добавления

Пирамидальная сортировка
С использованием пирамиды можно осуществить сортировку массива по следующему алгоритму.
Цикл i=0..N-1
Добавить(Массив[i]);
Цикл i=0..N-1
Массив[i] := ВершинаПирамиды;
Удалить ВершинуПирамиды;
Массив окажется отсортированным в силу того, что вершина пирамиды – это её наибольший элемент. Этот алгоритм напоминает сортировку методом прямого выбора, но с более эффективным поиском максимального элемента.

Реализация пирамиды на С++

Реализация добавления

Тестирование программы

Реализация вывода пирамиды в виде дерева

Вывод пирамиды в виде дерева

Реализация удаления вершины

Реализация пирамидальной сортировки - 1

Реализация пирамидальной сортировки - 2

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

Пример оптимизации перестановок