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

🎯 Зачем это нужно?

Представь, что ты разрабатываешь операционную систему 🖥️. Тебе нужно планировать задачи процессора - какую задачу выполнить следующей? Самую важную! Но как быстро найти самую важную из миллиона задач?

Или ты создаёшь рекомендательную систему для TikTok 📱. Из миллионов видео нужно быстро находить топ-10 самых подходящих пользователю. Обычная сортировка займёт слишком много времени!

Heapsort решает эти задачи элегантно: гарантирует O(n log n) в худшем случае (в отличие от quicksort) и сортирует “на месте” - не требует дополнительной памяти (в отличие от mergesort).

📚 История вопроса

В 1964 году Роберт Флойд изобрёл структуру данных “куча” (heap), но не для сортировки! Он решал задачу построения оптимальных префиксных кодов. А в том же году Дж. Уильямс независимо придумал heapsort как побочный продукт работы над приоритетными очередями.

Интересно, что heapsort долго считался “теоретически красивым, но практически медленным”. Сейчас его используют там, где критична предсказуемость времени работы - в embedded системах и real-time приложениях.

💡 Интуиция

Двоичная куча - это как турнирная сетка чемпионата мира по футболу ⚽, но наоборот!

В обычном турнире: много команд → меньше → финал → 1 победитель В куче: 1 лучший элемент наверху → больше элементов → ещё больше → все элементы внизу

[МЕДИА: image_01] Описание: Визуализация двоичной кучи как перевёрнутого турнира, где наверху максимальный элемент Промпт: “binary heap visualization as inverted tournament bracket, maximum element at top, tree structure with numbers, educational diagram, modern clean style, blue and orange colors”

Главная идея Heapsort:

1. Построй кучу из массива (самый большой элемент всплывёт наверх)
2. Извлекай максимум и помещай в конец массива
3. Восстанавливай кучу для оставшихся элементов
4. Повторяй, пока не закончатся элементы

Как будто ты играешь в “Царь горы” 🏔️ - сильнейший всегда наверху, убираешь его, и следующий сильнейший поднимается!

📐 Формальное определение

Двоичная куча - это почти полное двоичное дерево, где для каждого узла выполняется heap property:

• Max-heap: parent[i] ≥ left[i] и parent[i] ≥ right[i]
• Min-heap: parent[i] ≤ left[i] и parent[i] ≤ right[i]

Индексация в массиве (начиная с 0):

• parent(i) = ⌊(i-1)/2⌋
• left(i) = 2i + 1
• right(i) = 2i + 2

Алгоритм Heapsort:

def heapsort(arr):
    # 1. Построить max-heap
    build_max_heap(arr)
    
    # 2. Извлекать максимумы
    for i in range(len(arr)-1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]  # максимум в конец
        max_heapify(arr, 0, i)          # восстановить heap

Временная сложность: O(n log n) - всегда! Пространственная сложность: O(1) - сортировка на месте

🔍 Примеры с разбором

Пример 1: Сортировка массива [4, 10, 3, 5, 1]

Шаг 1: Строим max-heap

Исходный массив: [4, 10, 3, 5, 1]

    4
   / \
  10  3
 / \
5   1

Нарушение! 10 > 4, нужно исправить:

# Начинаем с последнего родителя: i = ⌊(5-1-1)/2⌋ = 1
max_heapify([4,10,3,5,1], 1, 5)  # узел 10 корректен
max_heapify([4,10,3,5,1], 0, 5)  # узел 4 нужно опустить

После heapify:

   10
   / \
  5   3
 / \
4   1

Массив: [10, 5, 3, 4, 1]

[МЕДИА: image_02] Описание: Пошаговая визуализация построения кучи из массива Промпт: “step-by-step heap construction visualization, showing array transformation into binary heap tree, arrows indicating swaps, numbers in nodes, educational style”

Шаг 2-6: Извлекаем максимумы

Итерация 1: Меняем 10↔1, heapify → [5,4,3,1|10] Итерация 2: Меняем 5↔1, heapify → [4,1,3|5,10]
Итерация 3: Меняем 4↔3, heapify → [3,1|4,5,10] Итерация 4: Меняем 3↔1 → [1|3,4,5,10]

Результат: [1, 3, 4, 5, 10] ✅

Пример 2: Зачем нужен heapify?

Рассмотрим массив [1, 2, 3, 4, 5, 6, 7]. Это уже отсортированный массив, но НЕ куча!

    1         Нужно:    7
   / \                 / \
  2   3        →      6   5  
 / \ / \             / \ / \
4 5 6  7            4 3 2  1

Build_max_heap превратит его в кучу за O(n), а не O(n log n)!

🎮 Практика

Базовый уровень 🟢

Задание 1: Построй max-heap из массива [3, 7, 1, 9, 2]

Задание 2: Какие индексы имеют дети узла с индексом 3 в массиве длины 10?

Задание 3: Является ли массив [20, 15, 8, 10, 5, 7, 6, 2, 9, 1] max-heap’ом?

Продвинутый уровень 🟡

Задание 4: Реализуй функцию max_heapify для узла i:

def max_heapify(arr, i, heap_size):
    # Твой код здесь

Задание 5: Модифицируй heapsort для сортировки по убыванию

Задание 6: Найди k-й максимальный элемент за O(n + k log n) используя heap

Челлендж 🔴

Задание 7: Почему build_max_heap работает за O(n), а не O(n log n)?

Задание 8: Реализуй heapsort с подсчётом сравнений и покажи, что в худшем случае их ≤ 2n log n

⚠️ Частые ошибки

❌ Ошибка: “Heapsort всегда быстрее quicksort” ✅ Правильно: Heapsort гарантирует O(n log n), но на практике часто медленнее quicksort 💡 Почему: У heapsort плохая константа и cache locality

❌ Ошибка: Путать heap (кучу) со stack (стеком)
✅ Правильно: Heap - дерево с heap property, stack - LIFO структура 💡 Почему: Разные названия в русском языке создают путаницу

❌ Ошибка: Неправильная индексация: parent(i) = i/2 ✅ Правильно: parent(i) = ⌊(i-1)/2⌋ для индексации с 0 💡 Почему: Формула parent(i) = ⌊i/2⌋ работает только при индексации с 1

❌ Ошибка: Забывать уменьшать heap_size после извлечения элемента ✅ Правильно: После swap(arr[0], arr[i]) делать heapify только для первых i элементов 💡 Почему: Иначе отсортированная часть массива испортится

🎓 Главное запомнить

✅ Heap = дерево с heap property: parent ≥ children (max-heap) ✅ Ключевая идея: строим кучу → извлекаем максимумы → получаем сортировку
✅ Гарантии: O(n log n) время, O(1) память, стабильная производительность ✅ Применение: там, где нужна предсказуемость (embedded, real-time системы)

🔗 Связь с другими темами

Откуда пришли: Структуры данных (урок 268) → двоичные деревья → heap Куда ведём: Приоритетные очереди → алгоритм Дейкстры → A* поиск Сравнение: Heapsort vs QuickSort vs MergeSort - разные компромиссы производительности Практика: Используется в STL (std::make_heap, std::sort_heap) и Python (heapq)