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

Пирамидальная сортировка (heap sort) – классический сравнивающий алгоритм сортировки, основанный на структуре «куча» (heap), реализуемый in-place и обладающий асимптотикой O(n log n) в худшем, среднем и лучшем случаях. Ключевая идея: сначала из массива строится бинарная куча (обычно макс-куча для сортировки по возрастанию), затем максимум, находящийся в корне, поочерёдно «вынимается» в конец массива, а оставшаяся часть снова «репарируется» (восстанавливается кучевое свойство).
Для подготовки к ЕГЭ эта тема ценна тем, что объединяет: представление структур данных в массиве, арифметику индексов, инварианты циклов, анализ сложности, корректность и практику работы с большими наборами данных.

Теоретические основы

1. Определение кучи
   

   Бинарная куча – почти полное бинарное дерево, удовлетворяющее кучевому свойству:

   • для макс-кучи каждый узел ≥ своих детей;

   • для мин-кучи – ≤ своих детей.
     Почти полнота дерева позволяет хранить кучу в обычном массиве без указателей.

2. Отображение кучи в массив (0-индексация)
   

   Для вершины с индексом i (0 ≤ i < n):

   • left(i) = 2*i + 1 – индекс левого ребёнка;

   • right(i) = 2*i + 2 – индекс правого ребёнка;

   • parent(i) = (i - 1) // 2 – индекс родителя (для i > 0).

   Примечание: при 1-индексации формулы упрощаются: left=2*i, right=2*i+1, parent=i//2, но в большинстве учебных языков ЕГЭ удобнее 0-индексация.

3. Базовые операции
   

   • siftDown (просеивание вниз): восстановление кучевого свойства на поддереве, корнем которого является i, при условии, что его поддеревья уже кучи.

   • siftUp (просеивание вверх): поднимает ключ вверх до восстановления свойства (используется при вставках; в heap sort применяем реже).

   • buildHeap (построение кучи): массовое «просеивание вниз» всех внутренних вершин от lastParent = (n-2)//2 до 0. Время – O(n).

   • extractMax (для макс-кучи): обмен корня с последним элементом текущей кучи, уменьшение размера кучи и siftDown(0).

4. Инварианты и корректность heap sort
   

   Алгоритм состоит из двух фаз:

   1. Построение макс-кучи на всём массиве a[0..n-1]. Инвариант: префикс a[0..heapSize-1] – корректная макс-куча.

   2. Итеративная выборка максимума:

   • swap(a[0], a[heapSize-1]) помещает глобальный максимум на позицию heapSize-1 (формирует отсортированный суффикс).

   • heapSize--, затем siftDown(0) восстанавливает макс-кучу на a[0..heapSize-1].
     Инвариант: после k шагов массив имеет вид
     [куча размера n-k][неубывающий отсортированный суффикс длины k].

5. Асимптотика и свойства
   

   • Построение кучи – O(n) (см. упражнение 4).

   • Каждая из (n−1) итераций извлечения максимума – O(log n), итого O(n log n).

   • Память – O(1) дополнительная (in-place).

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

   • Практически предсказуемое время (нет деградации до O(n²), как у быстрой сортировки)

Правила корректной реализации

1. Выбор кучи: для сортировки по возрастанию используйте макс-кучу; для убывания – мин-кучу.

2. Старт построения: начинайте siftDown с последнего внутреннего узла i = (n-2)//2 к 0; листья уже удовлетворяют свойству.

3. Границы: heapSize поддерживайте отдельно; при каждом «извлечении» уменьшайте его на 1. Все сравнения/доступы детей – только если индексы < heapSize.

4. Арифметика индексов: используйте 0-индексацию и явные проверки детей.

5. Сравнения: единый компаратор; при смене порядка сортировки меняйте критерий сравнения внутри siftDown.

6. Стабильность: если нужна стабильная сортировка, примените «украшение» ключей: сортируйте пары (ключ, исходный_индекс) (это делает итог эквивалентным стабильной сортировке, хотя сам алгоритм остаётся неустойчивым).

7. Без рекурсии: предпочтительно итеративный siftDown – надёжнее для больших n.

Псевдокод (0-индексация, сортировка по возрастанию)

HEAPSORT(a):

    n ← length(a)

    BUILD_MAX_HEAP(a, n)

    heapSize ← n

    while heapSize > 1:

        swap(a[0], a[heapSize-1])   // максимум на место

        heapSize ← heapSize - 1

        SIFT_DOWN(a, 0, heapSize)

BUILD_MAX_HEAP(a, n):

    for i ← (n-2)//2 downto 0:

        SIFT_DOWN(a, i, n)

SIFT_DOWN(a, i, heapSize):

    while true:

        left  ← 2*i + 1

        right ← 2*i + 2

        largest ← i

        if left  < heapSize and a[left]  > a[largest]: largest ← left

        if right < heapSize and a[right] > a[largest]: largest ← right

        if largest = i: break

        swap(a[i], a[largest])

        i ← largest

Вариант «дырки» (hole method) и «bottom-up sift down» уменьшают число сравнений, но идея та же.

Практические замечания и «острые углы»

• Повторы: равные элементы допустимы; результат корректен, но порядок равных не гарантирован.

• Типы данных: для объектов определяйте компаратор (</>), согласованный с отношением порядка.

• Почти отсортированные данные: в отличие от быстрой сортировки, heap sort не ускоряется – всё равно O(n log n).

• Кэш-локальность: «скачки» по массиву у кучи хуже, чем у merge sort/quick sort; на практике нередко проигрывает им по константам.

• Частичная сортировка: для поиска k-максимумов выгоднее использовать мин-кучу размера k над потоком.

Связь с ЕГЭ

• Структуры данных: массив, дерево, отображение дерева в массив.

• Алгоритмы: сортировки, восстановление инвариантов, инкрементальная корректность.

• Анализ сложности: вывод O(n) для build-heap и O(n log n) общего времени.

• Практика: задачи на топ-k, потоковую обработку, эффективную сортировку больших массивов в памяти.

Пять упражнений (с подробным разбором)

Упражнение 1. Построение макс-кучи по Флойду
Задание. Преобразуйте массив a = [4, 10, 3, 5, 1] в макс-кучу (0-индексация). Покажите шаги siftDown от i = (n-2)//2 к 0.
Решение.
n=5, lastParent=(5-2)//2=1.

• i=1: дети left=3 (5), right=4 (1). Наибольший – 5 (индекс 3) > a[1]=10? Нет, 10 больше 5 → изменений нет.

• i=0: дети 1 (10) и 2 (3). Наибольший – 10 (индекс 1) > 4 → swap(0,1) ⇒ [10, 4, 3, 5, 1].
  Новый i=1: дети 3 (5), 4 (1). Наибольший – 5 > 4 → swap(1,3) ⇒ [10, 5, 3, 4, 1].
  i=3 – лист, завершили.
  Итоговая куча: [10, 5, 3, 4, 1]. Проверка: каждый родитель ≥ детей.

Упражнение 2. Пошаговый heap sort
Задание. Отсортируйте по возрастанию a = [7, 2, 9, 1, 5]. Покажите: (1) построение кучи; (2) три первые итерации извлечения.
Решение (кратко).
Build:

• lastParent=(5-2)//2=1.

• i=1: дети 3(1),4(5) → max=5 → swap(1,4): [7,5,9,1,2].

• i=0: дети 1(5),2(9) → max=9 → swap(0,2): [9,5,7,1,2];
  i=2 – лист. Макс-куча: [9,5,7,1,2].

Извлечения:

1. swap(0,4): [2,5,7,1,9], heapSize=4 → siftDown(0): дети 1(5),2(7) → max=7 → swap(0,2): [7,5,2,1,9]; i=2 – лист.

2. swap(0,3): [1,5,2,7,9], heapSize=3 → siftDown(0): дети 1(5),2(2) → max=5 → swap(0,1): [5,1,2,7,9]; i=1: лист.

3. swap(0,2): [2,1,5,7,9], heapSize=2 → siftDown(0): дети 1(1) → max=2 (уже ок).
   Оставшиеся итерации дают итог: [1,2,5,7,9].

Упражнение 3. Топ-k с помощью кучи
Задание. Из потока чисел S = [12, 3, 25, 7, 9, 30, 18, 4] найдите три максимума за один проход и O(k) памяти.
Решение. Поддерживайте мин-кучу размера 3.

1. Добавляем 12 → heap=[12]

2. +3 → [3,12]

3. +25 → [3,12,25] (min-куча, корень=3)

4. +7 → сравнить с корнем(3): 7 > 3 ⇒ pop_min→[12,25], push 7 → heap=[7,25,12]

5. +9 → 9 > 7 ⇒ pop_min→[12,25], push 9 → [9,25,12]

6. +30 → 30 > 9 ⇒ pop_min→[12,25], push 30 → [12,25,30]

7. +18 → 18 > 12 ⇒ pop_min→[25,30], push 18 → [18,30,25]

8. +4 → 4 ≤ 18 ⇒ игнорируем.
   Итог кучи (в произвольном порядке): {18,25,30} – три максимума. Сортировка их при выводе займёт O(k log k).

Упражнение 4. Почему BUILD_MAX_HEAP работает за O(n)?
Задание. Обоснуйте O(n) для построения кучи методом Флойда.
Решение (эскиз). Высота узла определяет верхнюю оценку работы siftDown. В почти полном дереве:

• на высоте h (считая от листа) ≈ n / 2^{h+1} узлов;

• вклад: Σ_{h=0}^{⌊log n⌋} (n / 2^{h+1}) * h.
  Эта сумма ограничена сверху константой·n (классический результат: ≤ n).
  Следовательно, суммарная стоимость всех siftDown – O(n).

Упражнение 5. «Стабилизация» результата heapsort
Задание. Поясните, как получить результат, эквивалентный стабильной сортировке, не меняя сути heap sort.
Решение. Украсьте ключи парами (ключ, исходный_индекс) и сортируйте по лексикографическому порядку: сначала по ключу, затем по индексу. Тогда для равных ключей сохраняется исходный порядок. Минус: рост стоимости сравнения и необходимость хранить индексы; алгоритм всё ещё не «стабилен» по определению, но итог совпадает с устойчивой сортировкой по ключу.

Пример реализации (Python, по возрастанию)

def heap_sort(a):

    n = len(a)

    def sift_down(i, heap_size):

        while True:

            l = 2*i + 1

            r = 2*i + 2

            largest = i

            if l < heap_size and a[l] > a[largest]:

                largest = l

            if r < heap_size and a[r] > a[largest]:

                largest = r

            if largest == i:

                break

            a[i], a[largest] = a[largest], a[i]

            i = largest

    # Построение макс-кучи

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

        sift_down(i, n)

    # Итеративная выборка максимума

    heap_size = n

    while heap_size > 1:

        a[0], a[heap_size - 1] = a[heap_size - 1], a[0]

        heap_size -= 1

        sift_down(0, heap_size)

Заключение

Пирамидальная сортировка – строгий, детерминированный и предсказуемый алгоритм, который ценится за in-place реализацию и гарантию O(n log n) без провалов. Для ЕГЭ владение heap sort формирует важные компетенции: понимание представления деревьев в массиве, умение поддерживать инварианты, корректно работать с границами и анализировать сложность. На практике знание кучи расширяет инструментарий решения задач: от полной сортировки до потоковых топ-k и диспетчеризации приоритетов.