Heap sort строит бинарную кучу из массива, затем многократно извлекает максимум для получения отсортированного порядка. Работает за O(n log n) и является in-place.
Макс-куча держит наибольший элемент в корне. Постройте кучу (O(n)), затем поменяйте корень на конец, уменьшите кучу и восстановите кучу (sift down) — n раз.
import heapq
def heap_sort(arr):
heapq.heapify(arr) # min-heap in O(n)
return [heapq.heappop(arr) # pop smallest n times
for _ in range(len(arr))]
heap_sort([5, 2, 8, 1, 3]) # -> [1, 2, 3, 5, 8]
Классическая реализация делает это на месте путем sift down внутри массива.
Используйте, когда вам нужна гарантированная O(n log n) и O(1) дополнительная память (merge sort требует O(n); quicksort рискует O(n²)). Это нестабильная сортировка с плохой локальностью кэша, поэтому она часто медленнее на практике, чем quicksort. Та же куча питает приоритетные очереди и поиск top-k элементов.
Heap sort — единственная распространённая сортировка, которая одновременно гарантирует O(n log n) в худшем случае и работает in-place, что делает её ценной в условиях ограниченной памяти или гарантированных пределов.
Структура кучи под ней широко полезна — приоритетные очереди, алгоритм Дейкстры и потоковый top-k.
Она подкрепляет идею, что правильная структура данных делает алгоритм эффективным.