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