Пирамидальная сортировка. Алгоритм и его сложность

Гоша: Тимофей, ты говорил, что с использованием бинарной кучи можно реализовать алгоритм сортировки. Расскажешь как?

Тимофей: А ты хорошо разобрался с тем, как работает пирамида?

Гоша: Ну да!

Какая сложность вставки нового элемента в пирамиду в худшем случае?

O(n)

Сложность операции вставки нового элемента в пирамиду в худшем случае

O(\log n)

. Бинарная куча — это сбалансированное дерево, а максимум элемент может подняться до корня. Таким образом, на это потребуется

O(\log n)

операций.

O(1)

O(\log n)

O(n \log n)

Какая сложность извлечения самого приоритетного элемента из пирамиды в худшем случае?

O(n)

Сложность извлечения самого приоритетного элемента из пирамиды в худшем случае

O(\log n)

. В соответствии с алгоритмом, на место удаляемого элемента нужно поместить последний узел. Далее этот элемент в худшем случае может снова спуститься вниз. Сложность этой операции логарифмическая.

O(1)

O(\log n)

O(n \log n)

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

O(n \log n)

Разберёмся, как он работает.

Дан массив:

Скопировать кодPYTHON
arr = [3, 5, 1, 6, 9, 2]

Нужно отсортировать его за

O(n \log n)

в худшем случае.

Отсортирован ли массив, который представляет бинарную кучу?

Да, нужно сформировать бинарную кучу и получится отсортированный массив.

Массив, который представляет бинарную кучу, может быть несортированным. Выполнение свойства, что значение родителя приоритетнее значений дочерних узлов, не гарантирует, что массив отсортирован.

Нет, в общем случае этот массив не отсортирован.

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

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

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

Создадим бинарную кучу.
Вставим в неё элементы массива.
Будем извлекать из неё наиболее приоритетные элементы, удаляя их из кучи.

Рассмотрим алгоритм на примере, приведённом выше. Так выглядит вставка элементов из массива в бинарную кучу:

На этом шаге извлечём наиболее приоритетный элемент из кучи. По свойству пирамиды самый приоритетный элемент находится в вершине. Поэтому извлечём элемент из вершины, удаляя его из кучи. Для задачи сортировки по возрастанию приоритетный — минимальный элемент.

Таким образом, мы получили отсортированный массив.

Какая сложность у рассмотренного алгоритма в лучшем случае?

O(n)

Сложность пирамидальной сортировки в лучшем случае —

O(n \log n)

. Скоро разберёмся почему.

O(\log n)

O(n \log n)

O(n^2)

Какая сложность у рассмотренного алгоритма в худшем случае?

O(n)

Сложность пирамидальной сортировки в худшем случае также

O(n \log n)

O(\log n)

O(n \log n)

O(n^2)

Первый шаг — создание бинарной кучи. Сложность этой операции —

O(n)

. Нам просто нужно создать массив из n элементов.

Далее вставим

n

элементов в бинарную кучу.

Сложность этого этапа:

O(\log 1)+O(\log 2)+...+O(\log n) < O(\log n)+O(\log n)+...\\ ...+O(\log n) = O(n \log n)

Последним шагом извлекаем

n

элементов. Сложность этой операции также

O(n \log n)

O(\log n)+...+O(\log 2)+O(\log 1) < O(\log n)+...\\...+O(\log n)+O(\log n) = O(n \log n)

Получим:

T = O(n) + O(n \log n) + O(n \log n) = O(n \log n)

Это алгоритм сортировки, который в худшем случае работает за

O(n \log n)

Требуется ли для такой реализации дополнительная память?

Да

Верно. Для описанной реализации алгоритма пирамидальной сортировки нужно выделить память под массив из

n

элементов. То есть требуется

O(n)

дополнительной памяти.

Нет

Гоша: Здорово! Какой интересный алгоритм. Только я не понимаю, чем он лучше сортировки слиянием. Она тоже в худшем случае работает за

O(n \log n)

и требует

O(n)

дополнительной памяти.

Тимофей: Можно модифицировать алгоритм пирамидальной сортировки так, что не придётся выделять память под новый массив. Рассказать как?

Гоша: Нет, я хочу сам подумать, как это сделать. Если можно реализовать пирамидальную сортировку без использования дополнительной памяти, то почему в стандартных библиотеках многих языков программирования применяют быструю сортировку? Она ведь в худшем случае работает за квадратичное время. Не понимаю.

Тимофей: Быструю сортировку применяют чаще по двум причинам:

В алгоритме быстрой сортировки используется меньше операций обмена с памятью, чем в пирамидальной сортировке. Желательно избегать лишней работы с памятью.
$n$ обращений к последовательным ячейкам памяти исполняются быстрее, чем к случайным. Это связано с ограниченным количеством аппаратной кэш-памяти у процессоров. Некоторые алгоритмы могут быть дружелюбны к кэшу. Их называют cache-friendly. А некоторые — нет.

Пирамидальная сортировка — самая медленная из тех, которые работают за

O(n \log n)

Гоша: Ясно. Тогда я всегда буду выбирать быструю сортировку из этих трёх алгоритмов.

Тимофей: Мне кажется, это неправильное решение. Подбирать алгоритм нужно специально под задачу. Выбирай пирамидальную сортировку, если хочешь быть уверен, что алгоритм всегда будет работать за

O(n \log n)

, и в наличии нет

O(n)

дополнительной памяти. Кстати этот алгоритм сортировки был основным на компьютерах, выпускаемых в 1960–1970 годах.

Решите задачи G, H: https://contest.yandex.ru/contest/18996/problems/G/.