Heap Sort: O(n log n) с гарантией

Цели урока

• Понять структуру Heap и операцию heapify
• Объяснить, почему build-heap работает за O(n), а не O(n log n)
• Реализовать Heap Sort
• Понять trade-off: гарантия vs скорость на практике

Предварительные знания

• Куча (Heap)
• O(n log n) сортировки

• Куча (Heap)
• Merge Sort

Quick Sort быстр, но может деградировать до O(n²). Merge Sort всегда O(n log n), но требует O(n) памяти. Heap Sort - единственная сортировка, которая одновременно гарантирует O(n log n) и работает in-place. Почему же её почти никто не использует напрямую?

• **C++ std::sort (IntroSort)** - переключается на Heap Sort при глубокой рекурсии Quick Sort
• **Embedded systems** - предсказуемое время + мало памяти, нет сюрпризов
• **Priority Queue** - структура данных, лежащая в основе Heap Sort
• **Собеседования** - классика, проверяет понимание кучи

История Heap Sort

Heap Sort изобрёл Дж. У. Дж. Уильямс в 1964 году вместе с самой структурой данных Heap. В том же году Роберт Флойд (да, тот самый, Floyd-Warshall) улучшил алгоритм, предложив build-heap за O(n) вместо O(n log n). Это сделало алгоритм практически применимым.

Напоминание: что такое Heap

Корпоративная иерархия: директор сидит наверху, его подчинённые - ниже, их подчинённые - ещё ниже. **Heap (куча)** - именно такая структура, только с одним правилом: каждый «начальник» больше или равен своим «подчинённым».

• **Max-Heap:** родитель ≥ детей → корень = **максимум** всего дерева
• **Min-Heap:** родитель ≤ детей → корень = **минимум** всего дерева

Heap хранится в обычном массиве - никаких указателей. Позиция родителя и детей вычисляется по простым формулам:

**Ключевые операции:** insert O(log n), extract-max O(log n), build-heap O(n). Heap Sort использует именно build-heap и extract-max.

Heapify: восстановление свойства кучи

Новый элемент попал в корень без «собеседования» - хотя он хуже своих подчинённых. **Heapify** решает эту проблему: «опускает» нарушителя вниз, пока он не займёт правильное место.

**Heapify (sift-down)** принимает узел и предполагает, что оба поддерева уже являются корректными кучами. Он сравнивает узел с его детьми и, если нарушено свойство кучи, меняет узел с наибольшим ребёнком и повторяет процесс глубже.

**Сложность heapify:** O(log n) - в худшем случае элемент падает с корня до листа (высота дерева = log n).

Build Heap за O(n)

Как превратить произвольный массив в кучу? Наивная идея - вставлять элементы по одному за O(log n) каждый, итого O(n log n). Но есть способ лучше: **построить кучу за O(n)**, применяя heapify снизу вверх.

Листья (нижняя половина массива) уже являются кучами из одного элемента - их не нужно трогать. Начинаем с последнего не-листа и идём к корню, вызывая heapify на каждом узле:

**Почему O(n), а не O(n log n)?** Интуиция: большинство узлов - это листья или почти листья. Они находятся низко, значит heapify для них быстро завершается. Дорогие операции (heapify от корня) применяются к единицам узлов.

**Интуиция:** пирамида. Нижний ряд - самый широкий, но там нечего делать (листья). Верхний узел - самая долгая операция, но он один. Суммарно это O(n).

Алгоритм Heap Sort

Зная build-heap и heapify, алгоритм сортировки прост: корень max-heap всегда содержит максимальный элемент. Значит, чтобы отсортировать - нужно просто n раз «вытащить максимум» и поставить его на своё место в конце массива.

1. **Build max-heap** из массива - O(n)
2. **n-1 раз:** поменять корень (максимум) с последним элементом, уменьшить размер кучи, heapify корня - O(log n)

Анализ: сильные и слабые стороны

Heap Sort обладает уникальным сочетанием свойств: гарантированное O(n log n) в любом случае **и** O(1) дополнительной памяти. Ни Quick Sort, ни Merge Sort не могут похвастать обоими одновременно.

Почему тогда Heap Sort почти не используют напрямую? Проблема - **cache locality**. Quick Sort работает с соседними элементами (хорошо для кеша), Heap Sort постоянно прыгает между родителем и детьми по всему массиву.

**IntroSort** (используется в C++ `std::sort`) - умный гибрид: начинает как Quick Sort, но если рекурсия слишком глубокая (признак плохого pivot), переключается на Heap Sort. Так получаем скорость Quick Sort на практике + гарантию O(n log n) в худшем случае.

Heap Sort

• Build max-heap из массива - O(n), используя heapify снизу вверх
• Извлекаем максимум n раз: swap корня с хвостом + heapify - O(n log n)
• Гарантированное O(n log n) в любом случае
• O(1) дополнительной памяти - лучше Merge Sort
• На практике медленнее Quick Sort из-за cache misses
• Используется в IntroSort (C++ sort) как fallback

Связанные темы

Heap - мощная структура данных с множеством применений за пределами сортировки.

• Heap: структура данных — Основа Heap Sort
• Priority Queue — Главное применение Heap
• Quick Sort — Быстрее на практике, но без гарантий

Вопросы для размышления

• В каких сценариях heap sort предпочтительнее quicksort, несмотря на худшую константу?
• Как свойство max-heap используется в алгоритмах поиска k наибольших элементов?
• Почему in-place сортировка может быть критична в системах с ограниченной памятью?

Связанные уроки

• ds-14-heaps-intro — Heap Sort реализует build-heap + heapify - без понимания структуры кучи алгоритм непонятен
• ds-15-heap-applications — Priority Queue - главное применение кучи, и Heap Sort - демонстрация того, что из неё можно извлекать элементы по порядку
• alg-06-quick-sort — Quick Sort быстрее на практике из-за cache locality, Heap Sort гарантирует O(n log n) - это классический trade-off скорость vs предсказуемость
• alg-05-merge-sort — Merge Sort тоже гарантирует O(n log n), но требует O(n) памяти - Heap Sort выигрывает при ограниченной памяти
• alg-14-dijkstra — Алгоритм Дейкстры использует min-heap для эффективного извлечения ближайшей вершины - та же операция, что в Heap Sort