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

TL;DR

Пирамидальная сортировка (heapsort) сортирует массив в два этапа: сначала превращает его в max-кучу процедурой build-heap за [math]\displaystyle{ O(n) }[/math], затем [math]\displaystyle{ n-1 }[/math] раз меняет местами корень (текущий максимум) с последним элементом кучи и восстанавливает кучу sift-down за [math]\displaystyle{ O(\log n) }[/math]. Итог — гарантированное [math]\displaystyle{ O(n\log n) }[/math] в худшем случае при [math]\displaystyle{ O(1) }[/math] дополнительной памяти (данные переставляются на месте). По сравнению с быстрой сортировкой heapsort проигрывает в среднем из-за плохой локальности (прыжки по индексам дерева), зато не имеет «плохих» входов; по сравнению с сортировкой слиянием — не требует буфера, но неустойчив. Ключевые факты: build-heap линеен (сумма высот узлов даёт [math]\displaystyle{ O(n) }[/math], а не [math]\displaystyle{ O(n\log n) }[/math]), а оптимизация Флойда (bottom-up heapsort) экономит сравнения (на случайных данных — около 40 %). Подробнее о самой куче как структуре данных — в Двоичная куча; здесь разбирается именно сортировка.

Свойство	Значение
Класс	Сортировка сравнением; на месте (in-place)
Изобретение	Дж. Уильямс (J. W. J. Williams), 1964; линейный build-heap — Р. Флойд, 1964
Средний случай	[math]\displaystyle{ O(n\log n) }[/math]
Худший случай	[math]\displaystyle{ O(n\log n) }[/math]
Лучший случай	[math]\displaystyle{ O(n\log n) }[/math]
Build-heap	[math]\displaystyle{ O(n) }[/math]
Память	[math]\displaystyle{ O(1) }[/math] (не считая массива)
Устойчивость	нет
Число сравнений	[math]\displaystyle{ \approx 2n\log_2 n }[/math] в худшем (стандартный); bottom-up — меньше, на случайных данных [math]\displaystyle{ \approx 1.0\,n\log_2 n }[/math]
Структура	массив как почти полное (complete) двоичное дерево (max-куча)
Родственники	quicksort, mergesort, priority queue

Определения

Куча (heap) — почти полное (complete) двоичное дерево, в котором у каждого узла ключ не меньше ключей потомков (max-куча) или не больше (min-куча). Здесь рассматривается max-куча: максимум всегда в корне. Подробнее — в Двоичная куча.

Почти полное (complete) двоичное дерево — все уровни, кроме, возможно, последнего, заполнены, а последний — слева направо. Такое дерево укладывается в массив без указателей (см. рис. 1).

Представление массивом (0-базное). Для узла [math]\displaystyle{ i }[/math]: левый ребёнок [math]\displaystyle{ 2i+1 }[/math], правый [math]\displaystyle{ 2i+2 }[/math], родитель [math]\displaystyle{ \lfloor (i-1)/2 \rfloor }[/math]. Узел [math]\displaystyle{ i }[/math] — лист, если [math]\displaystyle{ 2i+1 \ge n }[/math].

Sift-down (просеивание вниз, Max-Heapify). Восстановление свойства кучи в поддереве с корнем [math]\displaystyle{ i }[/math], если оба его поддерева уже являются кучами: нарушитель обменивается с большим из детей и опускается дальше (см. рис. 3).

Sift-up (просеивание вверх). Восстановление кучи при вставке нового элемента в конец: элемент поднимается, пока больше родителя. Нужно для insert в очередь с приоритетом, но не для сортировки.

Build-heap (построение кучи). Превращение произвольного массива в кучу просеиванием вниз всех внутренних узлов от [math]\displaystyle{ \lfloor n/2 \rfloor - 1 }[/math] до [math]\displaystyle{ 0 }[/math] (см. рис. 4).

Пирамидальная сортировка (heapsort). Два этапа: (1) build-heap; (2) цикл извлечения максимума в конец массива с уменьшением размера кучи (см. рис. 5).

Bottom-up heapsort. Оптимизация Флойда: вместо двух сравнений на уровень (выбор ребёнка и сравнение с ним значения) сначала спускаются к листу, а затем поднимаются вверх, пока значение больше родителя (родитель меньше значения), — экономит сравнения: на случайных данных около 40 %, в худшем случае меньше.

Обозначения. [math]\displaystyle{ n }[/math] — размер массива; [math]\displaystyle{ h = \lfloor \log_2 n \rfloor }[/math] — высота дерева; [math]\displaystyle{ i, end }[/math] — индексы; [math]\displaystyle{ \log }[/math] — двоичный.

Мотивация и интуиция

Нужен алгоритм, который одновременно даёт гарантию [math]\displaystyle{ O(n\log n) }[/math] и не тратит лишней памяти. Сортировка слиянием гарантирует [math]\displaystyle{ O(n\log n) }[/math], но требует буфер [math]\displaystyle{ O(n) }[/math]; quicksort работает на месте, но в худшем случае даёт [math]\displaystyle{ \Theta(n^2) }[/math]. Heapsort закрывает обе потребности: куча — это массив, её максимум в корне, а восстановление кучи после извлечения стоит [math]\displaystyle{ O(\log n) }[/math].

Изюминка heapsort — линейное построение кучи. Наивно можно было бы вставлять элементы по одному через sift-up ([math]\displaystyle{ O(n\log n) }[/math]), но просеивание снизу вверх справляется за [math]\displaystyle{ O(n) }[/math]: большая часть узлов расположена высоко над листьями и почти не работает (см. рис. 2). Это редкий пример, когда обработка снизу вверх даёт оценку лучше наивной.

Ключевая идея в одном абзаце: куча даёт мгновенный доступ к максимуму (он в корне), а обмен корня с последним элементом постепенно переносит максимумы в отсортированный хвост. После каждого обмена размер кучи уменьшается, и sift-down восстанавливает её за высоту дерева. Цена — локальность: обращения к детям [math]\displaystyle{ 2i+1, 2i+2 }[/math] прыгают по памяти.

Рис. 1. Куча [9,7,5,3,1,4,2] как почти полное двоичное дерево и как массив: узел [math]\displaystyle{ i }[/math] лежит в [math]\displaystyle{ a[i] }[/math], его дети — в [math]\displaystyle{ a[2i+1] }[/math] и [math]\displaystyle{ a[2i+2] }[/math].

Рис. 2. Число узлов высоты [math]\displaystyle{ h }[/math] около [math]\displaystyle{ n/2^{h+1} }[/math], каждый просеивается не выше [math]\displaystyle{ h }[/math]; суммарная работа build-heap — [math]\displaystyle{ O(n) }[/math], а не [math]\displaystyle{ O(n\log n) }[/math].

Устройство

Пирамидальная сортировка опирается на две процедуры: sift-down (просеивание вниз) и build-heap (построение). Sift-down предполагает, что оба поддерева узла — уже кучи, и «проваливает» нарушителя вниз, всегда меняя его с большим ребёнком (см. рис. 3). Build-heap применяет sift-down к внутренним узлам от последнего к корню: к моменту обработки узла его поддеревья уже являются кучами, поэтому инвариант sift-down соблюдён.

Рис. 3. Sift-down для [3,9,7,5,4]: 3 меняется с большим ребёнком 9, затем с 5 и становится листом; результат [9,5,7,3,4].

Операции и алгоритмы

Операция: Sift-Down (Max-Heapify)

Идея. Сравнить узел с двумя детьми; если кто-то больше, обменять с большим и продолжить вниз от новой позиции.

Пошаговое описание:

Среди [math]\displaystyle{ i }[/math], [math]\displaystyle{ 2i+1 }[/math], [math]\displaystyle{ 2i+2 }[/math] (в пределах [math]\displaystyle{ n }[/math]) найти индекс максимума largest.
Если largest = i — остановиться (куча восстановлена).
Иначе обменять a[i] и a[largest], перейти к i = largest.

Инвариант. Перед каждым шагом поддеревья узла [math]\displaystyle{ i }[/math] — кучи; после шага свойство кучи в них сохранено, нарушение может остаться только в новом положении [math]\displaystyle{ i }[/math].

Процедура Sift-Down(a, n, i)
Вход:  массив a; размер кучи n; индекс i (0 ≤ i < n)
Выход: поддерево с корнем i — куча
Предусловие: поддеревья a[2i+1] и a[2i+2] — кучи
Сложность: O(log n)

1  while true
2      l ← 2i + 1 ; r ← 2i + 2 ; largest ← i
3      if l < n and a[l] > a[largest]
4          largest ← l
5      if r < n and a[r] > a[largest]
6          largest ← r
7      if largest = i
8          return
9      swap(a[i], a[largest])
10     i ← largest

Разбор. Для кучи [3,9,7,5,4] sift-down от корня меняет 3 с 9, затем 3 с 5, давая [9,5,7,3,4] (см. рис. 3).

Сложность. Не более [math]\displaystyle{ h = \lfloor\log_2 n\rfloor }[/math] шагов; на каждом — до двух сравнений.

Крайние случаи. Лист ([math]\displaystyle{ 2i+1 \ge n }[/math]) — ничего не делает. Один ребёнок — сравнение с ним.

Операция: Build-Max-Heap

Идея. Обработать внутренние узлы справа налево, вызывая sift-down; листья уже кучи.

Пошаговое описание:

Для i от [math]\displaystyle{ \lfloor n/2 \rfloor - 1 }[/math] до [math]\displaystyle{ 0 }[/math] вызвать Sift-Down(a, n, i).

Инвариант. После обработки узла [math]\displaystyle{ i }[/math] поддерево с корнем [math]\displaystyle{ i }[/math] — куча.

Процедура Build-Max-Heap(a)
Вход:  массив a[0..n−1]
Выход: a — max-куча
Сложность: O(n)

1  n ← length[a]
2  for i ← ⌊n/2⌋ − 1 downto 0
3      Sift-Down(a, n, i)

Разбор. [3,9,2,1,4,5] → после [math]\displaystyle{ i=2 }[/math]: [3,9,5,1,4,2]; [math]\displaystyle{ i=1 }[/math]: без изменений; [math]\displaystyle{ i=0 }[/math]: [9,4,5,1,3,2] (см. рис. 4).

Сложность. [math]\displaystyle{ O(n) }[/math]: число узлов высоты [math]\displaystyle{ h }[/math] около [math]\displaystyle{ n/2^{h+1} }[/math], стоимость [math]\displaystyle{ \le h }[/math]; [math]\displaystyle{ \sum_h (n/2^{h+1})h = n\sum h/2^{h+1} = O(n) }[/math].

Крайние случаи. [math]\displaystyle{ n \le 1 }[/math] — цикл пуст. Массив, уже являющийся кучей, всё равно просеивается, но без обменов.

Рис. 4. Build-heap для [3,9,2,1,4,5]: i=2, затем i=1 (без изменений), затем i=0; после просеивания корня — [9,4,5,1,3,2].

Операция: Heapsort (основной цикл)

Идея. Максимум кучи стоит в a[0]. Меняем его с последним элементом кучи, уменьшаем размер кучи и восстанавливаем её sift-down; максимум оказывается в отсортированном хвосте.

Пошаговое описание:

Build-Max-Heap(a).
Для end от [math]\displaystyle{ n-1 }[/math] до [math]\displaystyle{ 1 }[/math]: swap(a[0], a[end]); Sift-Down(a, end, 0).

Инвариант. После итерации end элементы a[end..n-1] — отсортированы и не меньше всех остальных; a[0..end-1] — куча.

Алгоритм Heapsort(a)
Вход:  массив a[0..n−1]
Выход: a отсортирован по неубыванию
Сложность: Θ(n log n) в лучшем, среднем и худшем случае; память O(1)

1  Build-Max-Heap(a)
2  for end ← length[a] − 1 downto 1
3      swap(a[0], a[end])
4      Sift-Down(a, end, 0)

Разбор. Куча [9,4,5,1,3,2]: end=5 → [5,4,2,1,3,9]; end=4 → [4,3,2,1,5,9]; end=3 → [3,1,2,4,5,9]; end=2 → [2,1,3,…]; end=1 → [1,2,3,4,5,9] (см. рис. 5).

Сложность. [math]\displaystyle{ n-1 }[/math] извлечений по [math]\displaystyle{ O(\log n) }[/math] → [math]\displaystyle{ O(n\log n) }[/math]; память [math]\displaystyle{ O(1) }[/math].

Крайние случаи. [math]\displaystyle{ n = 0, 1 }[/math] — ничего. Дубликаты обрабатываются корректно: значения встают по неубыванию, хотя порядок равных не сохраняется.

Рис. 5. Первые два шага heapsort для кучи [9,4,5,1,3,2]: максимум уходит в конец, sift-down восстанавливает кучу; хвост растёт справа.

Оптимизация: Bottom-up Heapsort (Флойд)

Идея. Обычный sift-down на каждом уровне делает до двух сравнений (выбрать большего ребёнка и сравнить с ним значение). В bottom-up-варианте сначала спускаются к листу, сравнивая только детей (одно сравнение на уровень), а затем поднимаются от листа, сравнивая значение с родителями и останавливаясь, как только оно встанет на место.

Пошаговое описание:

Сохранить val = a[i] и start = i.
Фаза 1 — спуск. Пока у текущего узла есть ребёнок: выбрать большего из детей, перенести его значение в текущий узел и перейти в этого ребёнка. Значение val ждёт в стороне и в сравнениях фазы 1 не участвует.
Фаза 2 — подъём. Начиная с листа, поднимать val: пока родитель меньше val, переносить родителя на место текущего узла; остановиться, когда родитель не меньше val или когда достигнут start.
Записать val в найденную позицию.

Инвариант. Поддеревья исходного узла start — кучи. В фазе 1 путь от start до текущего узла содержит значения, сдвинутые вверх, а val хранится отдельно. В фазе 2 все узлы ниже j на этом пути уже удовлетворяют свойству кучи, а val ищет место не выше start.

Процедура Sift-Down-Bottom-Up(a, n, i)
Вход:  массив a; размер кучи n; индекс i (поддеревья — кучи)
Выход: поддерево с корнем i — куча
Сложность: O(log n), сравнений меньше, чем у обычного sift-down

1  start ← i
2  val ← a[i]
3  c ← 2i + 1
4  while c < n                          # фаза 1: путь к листу
5      if c + 1 < n and a[c + 1] > a[c]
6          c ← c + 1
7      a[i] ← a[c]
8      i ← c
9      c ← 2i + 1
10 j ← i                                # i — лист, сюда можно поместить val
11 while j > start                      # фаза 2: подъём, пока parent < val
12     parent ← ⌊(j − 1) / 2⌋
13     if a[parent] ≥ val
14         break
15     a[j] ← a[parent]
16     j ← parent
17 a[j] ← val

Разбор. Возьмём [1,4,1,3,3], [math]\displaystyle{ n = 5 }[/math], [math]\displaystyle{ i = 1 }[/math]; тогда val = 4, start = 1.

Фаза 1: c = 3, правый ребёнок a[4] = 3 не больше левого a[3] = 3, поэтому c остаётся равным 3; a[1] ← a[3] = 3, массив [1,3,1,3,3], i = 3 — лист, цикл заканчивается.
Фаза 2: j = 3, parent = 1; a[1] = 3 < 4, поэтому a[3] ← 3, j = 1; цикл останавливается, потому что j дошёл до start = 1, а не потому, что родитель оказался не меньше val.
a[1] ← val = 4, массив снова [1,4,1,3,3].

Фаза 2 останавливается по достижении исходного корня, а не на первом сравнении; итог совпадает с исходным массивом, потому что значение уже стояло правильно.

Сложность. [math]\displaystyle{ O(\log n) }[/math]; на случайных массивах сравнений примерно на 40 % меньше, чем у стандартного heapsort (измерено кодом; зависит от входа). Для [math]\displaystyle{ n = 4096 }[/math] счётчики дают около [math]\displaystyle{ 1.74\,n\log_2 n }[/math] у стандартного варианта и около [math]\displaystyle{ 1.03\,n\log_2 n }[/math] у bottom-up, отношение [math]\displaystyle{ \approx 0.59 }[/math].

Крайние случаи. i — лист: фаза 1 не выполняется, фаза 2 тоже, val остаётся на месте. val уже не меньше детей: фаза 1 всё равно спускается к листу, а фаза 2 возвращает значение наверх. [math]\displaystyle{ n = 0 }[/math] или [math]\displaystyle{ 1 }[/math] — сортировать нечего. Дубликаты: сравнение строгое, устойчивость не гарантируется.

Bottom-up решает ту же задачу, что sift-down (см. рис. 3), но другим порядком обходов: сначала спуск к листу, затем подъём значения.

Сводная таблица сложности

Операция	Лучший	Средний	Худший	Память
`Sift-Down`	[math]\displaystyle{ \Theta(1) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(1) }[/math]
`Sift-Up` (вставка в кучу)	[math]\displaystyle{ \Theta(1) }[/math]	[math]\displaystyle{ \Theta(1) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(1) }[/math]
`Build-Max-Heap`	[math]\displaystyle{ \Theta(n) }[/math]	[math]\displaystyle{ \Theta(n) }[/math]	[math]\displaystyle{ \Theta(n) }[/math]	[math]\displaystyle{ O(1) }[/math]
`Heapsort`	[math]\displaystyle{ \Theta(n\log n) }[/math]	[math]\displaystyle{ \Theta(n\log n) }[/math]	[math]\displaystyle{ \Theta(n\log n) }[/math]	[math]\displaystyle{ O(1) }[/math]

Сноска к Sift-Up: для случайной вставки ожидаемое число подъёмов ограничено константой (вероятность подняться на [math]\displaystyle{ k }[/math] уровней [math]\displaystyle{ \approx 2^{-k} }[/math]); [math]\displaystyle{ O(\log n) }[/math] — худший случай.

Оговорка: heapsort не имеет «лёгких» входов — даже на отсортированном массиве выполняется полная работа, но и «тяжёлых» входов нет: оценка всегда [math]\displaystyle{ O(n\log n) }[/math].

Трассировка примера

Массив a = [3, 9, 2, 1, 4, 5], [math]\displaystyle{ n = 6 }[/math].

Построение кучи:

Шаг	Узел	Действие	Массив
старт	—	—	`3 9 2 1 4 5`
i = 2	2	2 < 5 → swap	`3 9 5 1 4 2`
i = 1	9	9 > 1, 9 > 4 — стоп	`3 9 5 1 4 2`
i = 0	3	3 < 9 → swap с 9; 3 < 4 → swap с 4	`9 4 5 1 3 2`

Основной цикл (куча [9,4,5,1,3,2]):

`end`	swap корня и `a[end]`	`Sift-Down(a, end, 0)`	Массив	Хвост
5	`[2,4,5,1,3,9]`	2→5	`5 4 2 1 3 9`	`9`
4	`[3,4,2,1,5,9]`	3→4	`4 3 2 1 5 9`	`5 9`
3	`[1,3,2,4,5,9]`	1→3	`3 1 2 4 5 9`	`4 5 9`
2	`[2,1,3,…]`	2 ≥ 1 — стоп	`2 1 3 4 5 9`	`3 4 5 9`
1	`[1,2,3,…]`	—	`1 2 3 4 5 9`	всё

Итог — [1,2,3,4,5,9]. Трассировка сверена с реализацией из раздела «Служебное».

Корректность и оценка сложности

Корректность Sift-Down

Утверждение. Если оба поддерева узла [math]\displaystyle{ i }[/math] — кучи, то после Sift-Down поддерево с корнем [math]\displaystyle{ i }[/math] — куча.

Доказательство. Если [math]\displaystyle{ a[i] }[/math] не меньше обоих детей, свойство выполняется (и в поддеревьях — по предположению). Иначе [math]\displaystyle{ a[i] }[/math] меняется с большим ребёнком [math]\displaystyle{ c }[/math]: теперь [math]\displaystyle{ a[i] \ge }[/math] прежнее значение ребёнка [math]\displaystyle{ \ge }[/math] второго ребёнка, значит, узел [math]\displaystyle{ i }[/math] удовлетворяет свойству. Поддерево [math]\displaystyle{ c }[/math] теряет свойство лишь в корне, но по индукции по высоте его восстанавливает рекурсивный вызов. [math]\displaystyle{ \square }[/math]

Корректность Build-Max-Heap

Индукция. Листья — кучи тривиально. При обработке узла [math]\displaystyle{ i }[/math] справа налево по индексам — от последнего внутреннего узла к корню — его поддеревья уже кучи (индексы [math]\displaystyle{ \gt i }[/math] обработаны), поэтому по лемме выше поддерево [math]\displaystyle{ i }[/math] становится кучей. После [math]\displaystyle{ i=0 }[/math] весь массив — куча. [math]\displaystyle{ \square }[/math]

Корректность Heapsort

Инвариант цикла. Перед итерацией с номером end массив a[0..end] — куча, а a[end+1..n-1] отсортирован и содержит [math]\displaystyle{ n-1-end }[/math] наибольших элементов. После swap(a[0], a[end]) и Sift-Down(a, end, 0) куча — a[0..end-1], а a[end..n-1] отсортирован.

База. Сразу после build-heap при end = n-1 весь массив a[0..n-1] — куча; хвост пуст, то есть отсортирован и содержит [math]\displaystyle{ 0 }[/math] наибольших элементов.

Шаг. Пусть перед итерацией a[0..end] — куча. Тогда a[0] — максимум a[0..end], и после обмена он оказывается в a[end]; вместе с прежним хвостом a[end+1..n-1] это даёт отсортированный a[end..n-1] из [math]\displaystyle{ n-end }[/math] наибольших элементов. Sift-down восстанавливает кучу в a[0..end-1] — условие инварианта для следующей итерации (end-1) выполнено.

Завершение. При end = 0 куча — a[0..0], а a[1..n-1] отсортирован; значит, отсортирован весь массив. [math]\displaystyle{ \square }[/math]

Линейность build-heap

Узел высоты [math]\displaystyle{ h }[/math] имеет не более [math]\displaystyle{ h }[/math] шагов sift-down. Число узлов высоты [math]\displaystyle{ h }[/math] в почти полном дереве из [math]\displaystyle{ n }[/math] узлов примерно [math]\displaystyle{ n/2^{h+1} }[/math]. Тогда

[math]\displaystyle{ \sum_{h=0}^{\log n} \frac{n}{2^{h+1}}\, h = \frac{n}{2}\sum_{h=0}^{\infty} \frac{h}{2^{h}} = \frac{n}{2}\cdot 2 = O(n). }[/math]

Значит, построение кучи линейно. Оценка heapsort: [math]\displaystyle{ O(n) + (n-1)O(\log n) = O(n\log n) }[/math].

Сравнение с альтернативами

Алгоритм	Средний	Худший	Память	Устойчивость	Локальность
Пирамидальная (heapsort)	[math]\displaystyle{ O(n\log n) }[/math]	[math]\displaystyle{ O(n\log n) }[/math]	[math]\displaystyle{ O(1) }[/math]	нет	плохая
Bottom-up heapsort	[math]\displaystyle{ O(n\log n) }[/math]	[math]\displaystyle{ O(n\log n) }[/math]	[math]\displaystyle{ O(1) }[/math]	нет	плохая (но меньше сравнений)
Быстрая	[math]\displaystyle{ O(n\log n) }[/math]	[math]\displaystyle{ O(n^2) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	нет	отличная
Слиянием (mergesort)	[math]\displaystyle{ O(n\log n) }[/math]	[math]\displaystyle{ O(n\log n) }[/math]	[math]\displaystyle{ O(n) }[/math]	да	хорошая
Introsort	[math]\displaystyle{ O(n\log n) }[/math]	[math]\displaystyle{ O(n\log n) }[/math]	[math]\displaystyle{ O(\log n) }[/math]	нет	отличная

Память quicksort указана средняя; в худшем случае стек рекурсии занимает [math]\displaystyle{ O(n) }[/math].

Рис. 6. Heapsort против quicksort, mergesort и introsort: гарантия [math]\displaystyle{ O(n\log n) }[/math] и [math]\displaystyle{ O(1) }[/math] памяти, но плохая локальность и неустойчивость.

Вердикт. Когда важна гарантия и ограничена память (встраиваемые системы, ядра) — heapsort (см. рис. 6). Когда важна средняя скорость — quicksort/introsort. Когда нужна устойчивость — mergesort/Timsort (см. Быстрая сортировка).

Где применяется

Куча и heapsort встречаются там, где нужен быстрый доступ к экстремуму или сортировка без лишней памяти (см. рис. 7).

Очереди с приоритетом. Двоичная куча — основа std::priority_queue, heapq (Python), PriorityQueue (Java) [8][9]; вставка/извлечение — [math]\displaystyle{ O(\log n) }[/math], просмотр максимума — [math]\displaystyle{ O(1) }[/math]. Почему: куча хранит экстремум в корне и не требует полной сортировки [1][5].
Сортировка на месте. Heapsort применяют там, где нельзя тратить [math]\displaystyle{ O(n) }[/math] буфера: встроенные системы, реального времени, ядра, обработка больших потоков. Почему: гарантия [math]\displaystyle{ O(n\log n) }[/math] при [math]\displaystyle{ O(1) }[/math] памяти [5].
Частичная сортировка и «k наибольших». Top-k через кучу размера [math]\displaystyle{ k }[/math] стоит [math]\displaystyle{ O(n\log k) }[/math] [4]; в Python это heapq.nlargest/nsmallest [9], тот же приём работает в потоковой обработке.
Алгоритмы на графах. Дейкстра и Прим на двоичной куче дают [math]\displaystyle{ O((n+m)\log n) }[/math]; Хаффман строит префиксный код на мини-куче. Почему: нужна повторяющаяся выборка минимума среди меняющегося множества [1][5].
Приоритетные планировщики. Обработка событий по времени, таймеры, арбитраж задач — всё, где нужен «ближайший» элемент; куча даёт логарифмические операции вставки/извлечения [5].

Рис. 7. Где применяется куча и heapsort: приоритетные очереди, сортировка на месте, top-k, алгоритмы на графах.

Историческая справка

Пирамидальную сортировку предложил Дж. У. Дж. Уильямс (J. W. J. Williams) в 1964 году (публикация Algorithm 232: Heapsort, Communications of the ACM); он же ввёл понятие пирамиды (кучи) [2]. В том же 1964 году Роберт Флойд (R. W. Floyd) показал, что кучу можно строить за линейное время (алгоритм Treesort), и предложил оптимизацию sift-down, известную как bottom-up heapsort [3]. Эти две работы сделали heapsort одним из стандартных алгоритмов сортировки; подробный анализ дал Дональд Кнут в The Art of Computer Programming, т. 3 (сортировка и поиск) [5].

Связанные улучшения: «слабые кучи» (weak heaps) и smoothsort Э. Дейкстры (1981), а также фибоначчиевы кучи (Фредман и Тарьян, 1987) [6] и биномиальные кучи (Ж. Вюйемен, 1978) [1] для быстрого слияния и decrease-key — см. Фибоначчиева куча, Биномиальная куча. Название «пирамидальная сортировка» — русский перевод английского heap («пирамида, куча»).

Типичные ошибки и подводные камни

Путаница 0- и 1-базной индексации. Формулы детей/родителя различаются; смешение даёт выход за границу и «почти отсортированный» массив.
Сравнение не с тем ребёнком. В sift-down нужно брать большего ребёнка (для max-кучи), иначе инвариант рушится.
Неверное начало build-heap. Начинать надо с [math]\displaystyle{ \lfloor n/2\rfloor - 1 }[/math] (последний внутренний узел), а не с [math]\displaystyle{ n-1 }[/math]: листья уже кучи.
Забыть уменьшить размер кучи. В цикле heapsort sift-down вызывается для размера end, а не [math]\displaystyle{ n }[/math]; иначе отсортированный хвост снова попадёт в кучу.
Sift-down без условия останова. Цикл должен завершаться, когда узел не меньше детей или стал листом.
Ожидание устойчивости. Heapsort неустойчив: обмен корня с последним меняет порядок равных. Пример: [2a, 2b, 1] → после heapsort [1, 2b, 2a] — равные 2a и 2b поменялись местами.
Ошибка в bottom-up-варианте. Нужны обе фазы (спуск к листу и подъём с подстановкой значения в «дырку») и ограничение подъёма исходным корнем; иначе теряются элементы.
Использование heapsort там, где важна скорость. Из-за локальности он обычно медленнее quicksort; для сортировки «по умолчанию» берут introsort.
Куча вместо кучи. std::make_heap/push_heap/pop_heap и std::priority_queue — разные инструменты; для сортировки всего массива есть std::sort_heap.
Переполнение индексов. При больших [math]\displaystyle{ n }[/math] 2*i+2 на грани int; следите за типом.

Задачи для практики

Sift-down. Реализуйте sift-down и проверьте, что он восстанавливает кучу для всех внутренних узлов снизу вверх. Подсказка: предусловие — поддеревья уже кучи.
Build-heap за O(n). Постройте кучу из случайного массива и подсчитайте сравнения; докажите, что их [math]\displaystyle{ O(n) }[/math]. Подсказка: сумма высот узлов.
Heapsort. Реализуйте heapsort и сравните с std::sort по корректности и числу сравнений. Подсказка: не забудьте уменьшать размер кучи.
Худший случай. Почему у heapsort нет [math]\displaystyle{ \Theta(n^2) }[/math]? Приведите аргумент через высоту. Подсказка: sift-down ≤ [math]\displaystyle{ h }[/math] шагов.
Bottom-up. Реализуйте bottom-up heapsort и измерьте экономию сравнений; на случайных данных ожидается порядка 40 %. Подсказка: две фазы, «дырка» в листе.
Top-k. Найдите [math]\displaystyle{ k }[/math] наибольших за [math]\displaystyle{ O(n\log k) }[/math] с кучей размера [math]\displaystyle{ k }[/math]. Ограничение: [math]\displaystyle{ O(k) }[/math] памяти. Подсказка: мини-куча на [math]\displaystyle{ k }[/math] элементов.
Средний случай. Постройте кучу из массива, отсортированного по возрастанию; сколько обменов делает sift-down? Подсказка: проанализируйте каждый уровень.
Decrease-key. Объясните, чем decrease-key в куче отличается от сортировки, и почему для Дейкстры нужна поддержка этого (см. Очередь с приоритетом). Подсказка: sift-up.

Связанные темы

Двоичная куча — куча как структура данных и очередь с приоритетом.
Биномиальная куча (план), Фибоначчиева куча (план) — кучи с быстрым слиянием.
Быстрая сортировка (план) — главный конкурент по скорости.
Сортировка слиянием (план) — устойчивая гарантия [math]\displaystyle{ O(n\log n) }[/math] ценой памяти [math]\displaystyle{ O(n) }[/math].
Асимптотическая сложность (план) — суммарные оценки и телескопирование.
Очередь с приоритетом (план) — абстрактный тип.
Алгоритм Дейкстры (план) — применение кучи на графах.

Источники

Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. Introduction to Algorithms (CLRS). 3rd ed. — MIT Press, 2009. — Гл. 6 «Heapsort» (heapify, build-heap, анализ).
Williams J. W. J. Algorithm 232: Heapsort // Communications of the ACM. — 1964. — Vol. 7, № 6.
Floyd R. W. Algorithm 245: Treesort // Communications of the ACM. — 1964. — Vol. 7, № 12 (линейное построение кучи; bottom-up).
Sedgewick R., Wayne K. Algorithms. 4th ed. — Addison-Wesley, 2011. — Гл. 2.4 (приоритетные очереди, heapsort).
Knuth D. E. The Art of Computer Programming. Vol. 3: Sorting and Searching. — Addison-Wesley, 2nd ed., 1998. — §5.2.3 (heapsort).
Fredman M. L., Tarjan R. E. Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms // Journal of the ACM. — 1987. — Vol. 34, № 3.
Wikipedia: Heapsort. URL: https://en.wikipedia.org/wiki/Heapsort.
cppreference: std::push_heap, std::sort_heap, std::priority_queue. URL: https://en.cppreference.com/w/cpp/algorithm/sort_heap.
Python documentation: heapq — Heap queue algorithm. URL: https://docs.python.org/3/library/heapq.html.

Поиск

Навигация

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

Содержание

TL;DR

Определения

Мотивация и интуиция

Устройство

Операции и алгоритмы

Операция: Sift-Down (Max-Heapify)

Операция: Build-Max-Heap

Операция: Heapsort (основной цикл)

Оптимизация: Bottom-up Heapsort (Флойд)

Сводная таблица сложности

Трассировка примера

Корректность и оценка сложности

Корректность Sift-Down

Корректность Build-Max-Heap

Корректность Heapsort

Линейность build-heap

Сравнение с альтернативами

Где применяется

Историческая справка

Типичные ошибки и подводные камни

Задачи для практики

Связанные темы

Источники