Heap Sort
Heap Sort — алгоритм сортировки через двоичную кучу: сначала строит max-heap, затем извлекает максимум.
Основная идея
Максимальный элемент хранится в корне кучи, переносим его в конец массива и восстанавливаем heap.
Пошаговый пример
Исходный массив:
[4, 10, 3, 5, 1]- Строим max-heap
- Меняем корень с последним элементом
- Повторяем heapify для оставшейся части
Псевдокод
build_max_heap(arr)
for end from n - 1 down to 1:
swap(arr[0], arr[end])
heapify(arr, 0, end)
Оптимизация: Хорош, когда нужна O(n log n) без дополнительной памяти O(n).
Сложность
Время
O(n log n) во всех случаях.
Память
O(1), in-place.
Когда используется
- Ограниченная память
- Гарантированная верхняя граница времени
- Системные задачи
Ключевые свойства
- Не стабильный
- In-place
- Предсказуемая сложность