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

Пирамидальная сортировка (также известная как сортировка кучей, Heapsort) — это алгоритм сортировки, основанный на структуре данных «куча» (heap). Относится к классу сортировок сравнением и гарантирует время выполнения O(n log n) в худшем, среднем и лучшем случаях. Алгоритм был предложен Джоном Уильямсом в 1964 году и является одним из первых алгоритмов сортировки с гарантированной оценкой O(n log n). Отличается тем, что не требует дополнительной памяти, кроме константного объёма (сортирует на месте, in-place), однако не является устойчивым (не сохраняет относительный порядок равных элементов).

История

Пирамидальная сортировка была разработана британским учёным-компьютерщиком Джоном Уильямсом (John William Joseph Williams) в 1964 году. Изначально алгоритм назывался «сортировка кучей» (heapsort). В 1964 году Уильямс опубликовал статью «Algorithm 232: Heapsort» в журнале Communications of the ACM, где впервые описал процедуру построения кучи и последующего извлечения максимума. Позднее, в 1970-х годах, Роберт Флойд (Robert W. Floyd) усовершенствовал алгоритм, предложив более эффективный способ построения начальной кучи (методом просеивания снизу вверх), который используется в современных реализациях. Пирамидальная сортировка стала одним из первых алгоритмов, доказавших, что сортировка сравнением может быть выполнена за O(n log n) в худшем случае с использованием только O(1) дополнительной памяти.

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

Алгоритм пирамидальной сортировки состоит из двух основных этапов:

1. Построение кучи (heapify) — преобразование исходного неупорядоченного массива в бинарную кучу (max-heap), где каждый родительский элемент не меньше своих потомков.
2. Сортировка — многократное извлечение максимального элемента (корня кучи) и его помещение в конец массива, с последующим восстановлением свойств кучи для оставшейся части.

Структура данных «куча»

Куча — это полное бинарное дерево, которое удовлетворяет свойству кучи: для любого узла его значение не меньше (в max-heap) или не больше (в min-heap) значений его дочерних узлов. В алгоритме пирамидальной сортировки используется max-heap. Массив представляется в виде дерева: для элемента с индексом i (при нумерации с 0) его левый потомок находится по индексу 2i + 1, правый — по индексу 2i + 2, а родитель — по индексу floor((i - 1) / 2).

Построение кучи

Начальная куча строится путём просеивания (sift-down) всех узлов, начиная с последнего узла, имеющего хотя бы одного потомка, и до корня. Для массива из n элементов последний узел с потомками имеет индекс floor(n/2) - 1. Для каждого такого узла выполняется процедура просеивания: если значение узла меньше значения одного из его потомков, узел меняется местами с наибольшим потомком, и процесс рекурсивно повторяется для нового положения узла. Этот метод, предложенный Робертом Флойдом, выполняется за O(n) операций, что является оптимальным.

Сортировка

После построения кучи корневой элемент (максимальный) меняется местами с последним элементом кучи. Размер кучи уменьшается на единицу (исключая отсортированный элемент из рассмотрения). Затем для нового корневого элемента выполняется просеивание, чтобы восстановить свойство кучи. Процесс повторяется, пока размер кучи не станет равным 1. В результате массив оказывается отсортированным по возрастанию.

Псевдокод

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

``` функция heapsort(A, n): // Построение кучи (max-heap) для i от n/2 - 1 до 0: siftDown(A, n, i)

// Сортировка для i от n - 1 до 1: обменять A[0] и A[i] siftDown(A, i, 0)

функция siftDown(A, n, i): // Просеивание элемента вниз largest = i left = 2i + 1 right = 2i + 2

если left < n и A[left] > A[largest]: largest = left если right < n и A[right] > A[largest]: largest = right

если largest != i: обменять A[i] и A[largest] siftDown(A, n, largest) ```

Анализ сложности

Временная сложность

• Худший случай: O(n log n). Алгоритм всегда выполняет построение кучи за O(n) и n-1 извлечений максимума, каждое из которых требует O(log n) времени на просеивание.
• Средний случай: O(n log n). Независимо от распределения входных данных, количество сравнений и перестановок остаётся в пределах O(n log n).
• Лучший случай: O(n log n). Даже если массив уже отсортирован, алгоритм всё равно выполняет полное построение кучи и n-1 извлечений. Однако в некоторых реализациях можно оптимизировать проверку, но в классическом варианте лучший случай не улучшается.

Пространственная сложность

• Дополнительная память: O(1). Алгоритм сортирует массив на месте, используя только константное количество дополнительной памяти (для переменных циклов и временного хранения при обмене).
• Стек вызовов: Рекурсивная реализация просеивания может потребовать O(log n) памяти для стека вызовов, но обычно используется итеративная версия, что даёт O(1).

Устойчивость

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

Реализация на языках программирования

Пример на C

```c

include <stdio.h>

void swap(int a, int b) { int temp = a; a = b; b = temp; }

void siftDown(int arr[], int n, int i) { int largest = i; int left = 2 i + 1; int right = 2 i + 2;

if (left < n && arr[left] > arr[largest]) largest = left; if (right < n && arr[right] > arr[largest]) largest = right;

if (largest != i) { swap(&arr[i], &arr[largest]); siftDown(arr, n, largest); } }

void heapsort(int arr[], int n) { // Построение кучи for (int i = n / 2 - 1; i >= 0; i--) siftDown(arr, n, i);

// Сортировка for (int i = n - 1; i > 0; i--) { swap(&arr[0], &arr[i]); siftDown(arr, i, 0); } } ```

Пример на Python

```python def sift_down(arr, n, i): largest = i left = 2 i + 1 right = 2 i + 2

if left < n and arr[left] > arr[largest]: largest = left if right < n and arr[right] > arr[largest]: largest = right

if largest != i: arr[i], arr[largest] = arr[largest], arr[i] sift_down(arr, n, largest)

def heapsort(arr): n = len(arr)

Построение кучи

for i in range(n // 2 - 1, -1, -1): sift_down(arr, n, i)

Сортировка

for i in range(n - 1, 0, -1): arr[0], arr[i] = arr[i], arr[0] sift_down(arr, i, 0) ```

Сравнение с другими алгоритмами

Быстрая сортировка (Quicksort)

• Сложность: Quicksort в среднем случае O(n log n), но в худшем случае (например, на уже отсортированном массиве) может деградировать до O(n²). Пирамидальная сортировка гарантирует O(n log n) в любом случае.
• Память: Quicksort использует O(log n) дополнительной памяти для рекурсивных вызовов (в среднем), пирамидальная сортировка — O(1).
• Скорость: На практике Quicksort обычно быстрее пирамидальной сортировки из-за лучшей локальности обращений к памяти (cache-friendly). Пирамидальная сортировка часто проигрывает из-за большого количества операций обмена и просеивания, а также плохой работы с кэшем процессора.

Сортировка слиянием (Mergesort)

• Сложность: Оба алгоритма имеют гарантированное O(n log n).
• Память: Mergesort требует O(n) дополнительной памяти для временных массивов, пирамидальная сортировка — O(1).
• Устойчивость: Mergesort устойчив, пирамидальная сортировка — нет.

Сортировка вставками/выбором

• Сложность: O(n²) в худшем случае, что значительно медленнее для больших n.
• Память: O(1), как и у пирамидальной сортировки.
• При малых размерах массивов (менее 10-20 элементов) сортировка вставками может быть быстрее из-за меньших накладных расходов.

Применение

Пирамидальная сортировка используется в ситуациях, когда:

• Требуется гарантированное время выполнения O(n log n) в худшем случае (например, в системах реального времени, где недопустимы выбросы времени выполнения).
• Ограничена доступная память (встраиваемые системы, микроконтроллеры), так как алгоритм не требует дополнительных массивов.
• Необходимо избежать рекурсивных вызовов (итеративная реализация проста).
• Важна предсказуемость времени работы.

Однако на практике пирамидальная сортировка уступает быстрой сортировке (Quicksort) и интроспективной сортировке (Introsort, гибрид Quicksort и Heapsort) по скорости на большинстве наборов данных. Introsort, используемый в стандартной библиотеке C++ (std::sort), при обнаружении рекурсивной глубины, превышающей O(log n), переключается на пирамидальную сортировку, чтобы избежать деградации до O(n²).

Интересные факты

• Пирамидальная сортировка является одним из немногих алгоритмов, которые одновременно имеют гарантированное время O(n log n) и константную дополнительную память.
• Структура данных «куча», лежащая в основе алгоритма, также используется для реализации очередей с приоритетом (priority queue).
• Алгоритм может быть модифицирован для сортировки по убыванию путём построения min-heap вместо max-heap.
• В 1990-х годах был предложен вариант Smoothsort (сглаженная сортировка) Эдсгером Дейкстрой, который является адаптивной версией пирамидальной сортировки и показывает O(n) на частично отсортированных данных.

Источники

• Williams, J. W. J. (1964). Algorithm 232: Heapsort. Communications of the ACM, 7(6), 347-348.
• Floyd, R. W. (1964). Algorithm 245: Treesort. Communications of the ACM, 7(12), 701.
• Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. (2013). Алгоритмы: построение и анализ (3-е изд.). М.: Вильямс.
• Кнут, Д. Э. (2000). Искусство программирования. Том 3. Сортировка и поиск (2-е изд.). М.: Вильямс.