Слайд 2Пирамида
Пирамида является структурой данных, позволяющей обратиться к наибольшему элементу за время O(1),
а также позволяющая удалять наибольший элемент и вставлять новый элемент за время O(log2N).
Пирамида – это разновидность двоичного дерева, обладающего двумя свойствами. Первое свойство заключается в том, что любой узел такого дерева больше либо равен любого из своих потомков.
Это свойство называется свойством слабой упорядоченности.
Слайд 4Свойство полноты
Второе свойство называется свойством полноты и заключается в том, что это
дерево содержит все возможные узлы при заполнении слева направо и сверху вниз.
На рисунке слева изображено полное (Complete) дерево, а справа – неполное (Incomplete).
Слайд 5Пирамида на основе массива
Наиболее простой реализацией пирамиды является реализация на основе массива.
При
этом каждому узлу дерева соответствует конкретная ячейка массива.
Именно свойство полноты позволяет осуществить такое отображение (обеспечить отсутствие «дыр» в массиве).
Слайд 6Пример пирамиды на основе массива
Слайд 7Связь между деревом и массивом
Благодаря такому отображению для любого узла можно определить
индексы его родителя и потомков. Пусть i – индекс некоторого узла в массиве, тогда
индекс родителя равен (i-1) /2;
индекс левого потомка равен 2*i+1;
индекс левого потомка равен 2*i+2.
В качестве упражнения проверьте эти формулы для приведённого рисунка.
Слайд 8Реализация операций
Рассмотрим теперь, как реализуются операции взятия наибольшего элемента, вставки нового элемента
и удаления наибольшего.
Для обращения к наибольшему элементу пирамиды достаточно взять первый элемент массива.
Операции вставки нового элемента и удаления наибольшего элемента несколько сложнее, то осуществляются быстро – за время O(log2N).
Слайд 9Удаление вершины
Поскольку удаляется первый элемент, то в массиве образуется «дыра», и возникает
необходимость исключить её, восстановив тем самым полноту дерева. Для этого существует следующий алгоритм:
переместить последний узел в корень (на место удаленного);
смещать его вниз до тех пор, пока он не окажется на подходящем месте (меньше либо равен родители и больше либо равен потомков).
При смещении вниз, очевидно, существуют две альтернативы: влево или вправо. Так вот смещать следует в сторону большего из этих двух узлов, чтобы не нарушить слабую упорядоченность.
Слайд 11Добавление нового элемента
Рассмотрим теперь операцию добавления нового элемента.
Сложность этой процедуры состоит
в том, что после добавления должна быть сохранена слабая упорядоченность дерева.
Алгоритм добавления похож на алгоритм удаления и состоит из следующих шагов:
поместить новый узел на последнюю позицию;
смещать его вверх до тех пор, пока он не станет меньше либо равен своего родителя.
Слайд 13Пирамидальная сортировка
С использованием пирамиды можно осуществить сортировку массива по следующему алгоритму.
Цикл
i=0..N-1
Добавить(Массив[i]);
Цикл i=0..N-1
Массив[i] := Вершина Пирамиды;
Удалить Вершину Пирамиды;
Массив окажется отсортированным в силу того, что вершина пирамиды – это её наибольший элемент. Этот алгоритм напоминает сортировку методом прямого выбора, но с более эффективным поиском максимального элемента.
Слайд 17Реализация вывода пирамиды в виде дерева
Слайд 20Реализация пирамидальной сортировки - 1
Слайд 21Реализация пирамидальной сортировки - 2