Алгоритм HeapSort

Двухфазная сортировка: Phase 1 — heapify массива O(n), Phase 2 — n раз extract-max O(log n) с помещением максимума в конец. Итого O(n log n) гарантированно (нет худшего случая O(n²) как у QuickSort). In-place O(1) память (используем сам массив как heap). Не стабильная (порядок равных может измениться). Изобретена Williams 1964, улучшена Floyd 1964 (heapify O(n)). Хуже QuickSort на практике (cache misses из-за прыжков по памяти), но детерминирована