DEV//UNIT
← АлгоритмыSorting

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

Max-heap: корень — всегда максимум. Извлекаем корень в хвост, просеиваем — O(n log n) на месте.

время O(n log n)память O(1)уровень: начальный
Что происходит сейчас0/0
Нажмите Play, чтобы запустить сценарий
TypeScript — активная строка подсвечена шагом
1function heapSort(a: number[]): number[] {
2  const n = a.length
3 
4  // построение max-heap
5  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
6    siftDown(a, i, n)
7  }
8 
9  // перенос корня в конец
10  for (let end = n - 1; end > 0; end--) {
11    swap(a, 0, end)
12    siftDown(a, 0, end)
13  }
14 
15  return a
16}
17 
18function siftDown(a: number[], i: number, size: number): void {
19  while (true) {
20    const l = 2 * i + 1
21    const r = 2 * i + 2
22    let largest = i
23    if (l < size && a[l] > a[largest]) largest = l
24    if (r < size && a[r] > a[largest]) largest = r
25    if (largest === i) return
26    swap(a, i, largest)
27    i = largest
28  }
29}

Проблема

Гарантия O(n log n) БЕЗ дополнительной памяти (в отличие от слияния). Куча — двоичное дерево в массиве: родитель ≥ детей, максимум всегда в корне.

Что вы видите

Дерево: построение кучи просеиванием вниз, затем цикл — корень (максимум) обменивается с последним узлом кучи, уходит в отсортированный хвост, новый корень просеивается на место.

Как это работает

Куча живёт в массиве: дети i — это 2i+1 и 2i+2. siftDown: больший из детей поднимается, пока инвариант не восстановится — O(log n). Построение — O(n). Извлечения n раз по O(log n). Итог: гарантия n log n на месте, но неустойчиво и с плохой локальностью кэша.

Пошаговый разбор

  1. 01

    Построение

    От середины к корню: siftDown каждого узла.

  2. 02

    Куча готова

    Родитель ≥ детей везде.

  3. 03

    Извлечение

    Корень-максимум ↔ последний узел кучи.

  4. 04

    Просеивание

    Новый корень уходит вниз до места.

  5. 05

    Повтор

    Хвост отсортированной части растёт.

Complexity и ограничения

time
O(n log n)
space
O(1)

Гарантия O(n log n), память O(1). Неустойчива, кэш-недружелюбна (медленнее quick на практике).

Edge cases

  • Уже отсортирован

    Всё равно n log n — кучу придётся строить.

  • Все равные

    Работает, но много холостых просеек.

  • n = 1

    Куча из одного — тривиальна.

Где встречается в реальности

Приоритетные очереди

Куча — структура данных: планировщики, Dijkstra, A*.

Топ-K из потока

Куча размера K держит наибольшие_seen.

Таймеры

Ближайший дедлайн — корень кучи.

Связанные алгоритмы

Сортировка слияниемБыстрая сортировка
Shorts

«Дерево, которое сортирует: куча»

Тот же сценарий StepSequence в вертикальной композиции — с safe zones и записью WebM ниже на странице.

Shorts 9:16

Вертикальная композиция строится той же последовательностью шагов, что и страница: safe zones отмечены пунктиром (там живёт UI платформ), биты сценария подсвечиваются по прогрессу. Кнопка записи сохраняет WebM — детерминированная StepSequence даёт воспроизводимый ролик без монтажа.

Дерево, которое сортирует: куча
Нажмите Play
Бит 1/6 · 0–2 с
Hook
script-setup.ru/algorithms/heap-sort