Пирамидальная сортировка как работает

Geek Notes

заметки/статьи/переводы на темы программирования, алгоритмов и etc.

Алгоритм пирамидальной сортировки (сортировка кучей)

Mar 4 th , 2015 8:56 pm

Далее представлен краткий конспект разбора пирамидальной сортировки по книге «Алгоритмы. Построение и анализ» (Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн). Примеры кода написаны на языке Java.

Время работы — O(n*logn).
Свойства:

• Не требует дополнительной памяти, работает с тем же массивом данных.
• Используется структура данных — Двоичное дерево (куча) .

Принцип работы:

1. Строим пирамиду
2. Сохраняем размер массива в отдельную переменную
3. Так как максимальный элемент находится в корне т.е. a[0], то меняем местами с последним элементом массива, и уменьшаем размер переменной в которой у нас записан размер массива
4. Вызываем метод поддержки свойств пирамиды heapify(array, 0)

Бинарное дерево с максимальным элементом в корне

Представление бинарного дерева в виде массива

Родитель и потомки любого узла вычисляются по следующем методам:

Метод поддержки свойств пирамиды:

Пример работы

Метод создания пирамиды

Пример работы построения кучи из массива A

Метод сортировки:

Пример работы алгоритма пирамидальной сортировки

Алгоритмы сортировки. HeapSort

Ну вот и дошли до алгоритма, в котором начинаем говорить о структурах даных. HeapSort это усовершенствованный SelectionSort, но работающей с кучей ( heap ). Этот алгоритм немного медленее чем QuickSort, на даже в самом худшем случае имеет сложность O(nlogn), в отличии от того же QuickSort который деградирует аж до O(n^2).

Итак, что такое куча? Heap — это деревообразная структура, в которой выполняется одно правило: если элемент B потомок элемента А, то значение A > B.

Одной из реализаций heap— может быть binary heap( двоичная куча ) , в котором выполняется такие условия:

1. Значение отцов больше чем значение потомков ( max-heap, существует еще min-heap где все наоборот☺ )
2. Глубина листьев отличается не больше чем на 1 слой
3. Последний слой заполняется с лево на право.

Удобной структурой для хранения сортирующей кучи ( так еще называют binary heap ) — является массив, у которого первый элемент a[0] — корень дерева ( то есть самый большой элемент ) .

Для начала, давайте построим саму структуру даных. То что я встречал в практике, делиться на 2 типа:

1. Построение структуры с ее методами, и тому подобное ( ООП языки, Сейджвик, все дела)
2. Простое использование массива, с дополнительными методами

ООП реализацию кучи мы обязательно обсудим в следующем посту, потому сегодня просто используем метод 2.

Итак, для начала нам необходимо написать метод, который из несортированого массива сделает кучу:

Как видим, у нас есть функция build_heap которая начиная с половины массива, вызывает функцию sink. Функция sink бегает по всем детям листа который мы указали и проверяет или они действительно меньше, если нет — меняем элементы местами. После того как пробежались по всем детям, и детям его детей, и … мы возвращаемся, и начинаем проверять у элемента перед проверенным, и так да самого первого элемента. В результате мы получаем бинарную кучу, с самым большим элементом находящемся на первом месте.

С половины мы начинаем, чтоб точно проверить все элементы☺

Сам код сортировки невероятно простой:

Мы просто берем первый элемент, и меняем его местами с последним, таким образом в самом низу у нас оказывается самый большой элемент. После этого для вызывается sink для первого элемента, в результате которого корнем стает самый большой элемент в массиве, не считая последнего. И так до самого первого элемента.

Собственно, как видно на гифке в начале из массива строится бинарная куча, а уже после этого сортируется.

К сожалению, венгерского танца heapsort я не нашел, потому вам немного модерна:

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

Метод пирамидальной сортировки, изобретенный Д. Уилльямсом, является улучшением традиционных сортировок с помощью дерева.

Пирамидой ( кучей ) называется двоичное дерево такое, что

a[i] ≤ a[2i+1];

a[i] ≤ a[2i+2].

Подробнее

a[0] — минимальный элемент пирамиды.

Общая идея пирамидальной сортировки заключается в том, что сначала строится пирамида из элементов исходного массива, а затем осуществляется сортировка элементов.

Выполнение алгоритма разбивается на два этапа.

1 этап Построение пирамиды. Определяем правую часть дерева, начиная с n/2-1 (нижний уровень дерева). Берем элемент левее этой части массива и просеиваем его сквозь пирамиду по пути, где находятся меньшие его элементы, которые одновременно поднимаются вверх; из двух возможных путей выбираете путь через меньший элемент.

Например, массив для сортировки

24, 31, 15, 20, 52, 6

Расположим элементы в виде исходной пирамиды; номер элемента правой части (6/2-1)=2 — это элемент 15.

Результат просеивания элемента 15 через пирамиду.

Следующий просеиваемый элемент – 1, равный 31.

Затем – элемент 0, равный 24.

Разумеется, полученный массив еще не упорядочен. Однако процедура просеивания является основой для пирамидальной сортировки. В итоге просеивания наименьший элемент оказывается на вершине пирамиды.

2 этап Сортировка на построенной пирамиде. Берем последний элемент массива в качестве текущего. Меняем верхний (наименьший) элемент массива и текущий местами. Текущий элемент (он теперь верхний) просеиваем сквозь n-1 элементную пирамиду. Затем берем предпоследний элемент и т.д.

Продолжим процесс. В итоге массив будет отсортирован по убыванию.

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

Результат выполнения

Анализ алгоритма пирамидальной сортировки

Несмотря на некоторую внешнюю сложность, пирамидальная сортировка является одной из самых эффективных. Алгоритм сортировки эффективен для больших n. В худшем случае требуется n·log₂n шагов, сдвигающих элементы. Среднее число перемещений примерно равно

Пирамидальная сортировка (HeapSort)

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

Что такое двоичная куча?

Давайте сначала определим законченное двоичное дерево. Законченное двоичное дерево — это двоичное дерево, в котором каждый уровень, за исключением, возможно, последнего, имеет полный набор узлов, и все листья расположены как можно левее (Источник Википедия).

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

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

Поскольку двоичная куча — это законченное двоичное дерево, ее можно легко представить в виде массива, а представление на основе массива является эффективным с точки зрения расхода памяти. Если родительский узел хранится в индексе I, левый дочерний элемент может быть вычислен как 2 I + 1, а правый дочерний элемент — как 2 I + 2 (при условии, что индексирование начинается с 0).

Алгоритм пирамидальной сортировки в порядке по возрастанию:

1. Постройте max-heap из входных данных.
2. На данном этапе самый большой элемент хранится в корне кучи. Замените его на последний элемент кучи, а затем уменьшите ее размер на 1. Наконец, преобразуйте полученное дерево в max-heap с новым корнем.
3. Повторяйте вышеуказанные шаги, пока размер кучи больше 1.

Как построить кучу?

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