Сортировка кучей (Пирамидальная сортировка)
Алгоритм сортировки, основанный на структуре данных «куча» (heap), даёт гарантированное время O(n log n) в любом случае.
Идея алгоритма
Из массива строится двоичная куча (обычно максимальная). Максимальный элемент (корень кучи) находится в начале массива. Мы меняем его местами с последним элементом, уменьшаем размер кучи и восстанавливаем свойство кучи (операция heapify). Повторяя этот процесс, мы получаем отсортированный массив.
Асимптотика:
- Время (худший / средний / лучший случай): O(n log n)
- Память: O(1) — сортировка «на месте»
- Не является стабильной сортировкой
Когда использовать
- Когда важна гарантированная сложность O(n log n);
- Когда нельзя выделять дополнительную память под массив;
- Когда стабильность сортировки не критична.
Плюсы
- Гарантированное время работы O(n log n);
- Работает in-place, не требует дополнительной памяти;
- Проста идея, основанная на структуре «куча».
Минусы
- Часто медленнее быстрой сортировки на реальных данных;
- Не стабильная сортировка;
- Реализация чуть сложнее, чем у простых алгоритмов.
Пример кода
function heapify(a, n, i) {
let largest = i;
const left = 2 * i + 1;
const right = 2 * i + 2;
if (left < n && a[left] > a[largest]) largest = left;
if (right < n && a[right] > a[largest]) largest = right;
if (largest !== i) {
[a[i], a[largest]] = [a[largest], a[i]];
heapify(a, n, largest);
}
}
export function heapSort(arr) {
const a = [...arr];
const n = a.length;
// строим кучу
for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
heapify(a, n, i);
}
// вытаскиваем максимум в конец
for (let i = n - 1; i > 0; i--) {
[a[0], a[i]] = [a[i], a[0]];
heapify(a, i, 0);
}
return a;
}Попробуй самостоятельно написать алгоритм, а затем сравнить
Полезные темы
Рекомендуем изучить эти темы для лучшего понимания