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

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) экономит примерно четверть сравнений. Подробнее о самой куче как структуре данных — в Двоичная куча; здесь разбирается именно сортировка.

Свойство	Значение
Класс	Сортировка сравнением; на месте (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] (стандартный), [math]\displaystyle{ \approx 1.5\,n\log_2 n }[/math] (bottom-up)
Структура	массив как полное двоичное дерево (max-куча)
Родственники	quicksort, mergesort, priority queue

Определения

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

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

Представление массивом (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. Оптимизация Флойда: вместо двух сравнений на уровень (выбор ребёнка и сравнение с ним значения) сначала спускаются к листу, а затем поднимаются вверх, пока значение меньше родителя, — экономит порядка четверти сравнений.

Обозначения. [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. Полное двоичное дерево хранится в массиве; инвариант max-кучи: родитель не меньше детей.

Рис. 2. Узлов высоты [math]\displaystyle{ h }[/math] примерно [math]\displaystyle{ n/2^{h+1} }[/math], каждый стоит [math]\displaystyle{ \le h }[/math] спусков; сумма [math]\displaystyle{ \le 2n }[/math].

Устройство

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

Рис. 3. Нарушитель меняется с большим ребёнком и опускается до места; стоимость [math]\displaystyle{ O(\log n) }[/math].

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

Операция: 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. Просеиваем внутренние узлы от середины к корню; суммарно [math]\displaystyle{ O(n) }[/math].

Операция: 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 отсортирован по неубыванию
Сложность: O(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. Максимум уходит в конец, куча уменьшается, sift-down восстанавливает её.

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

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

Процедура 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: подъём на своё место
12     parent ← (j − 1) / 2
13     if a[parent] ≥ val
14         break
15     a[j] ← a[parent]
16     j ← parent
17 a[j] ← val

Разбор. При [math]\displaystyle{ i=1 }[/math] в куче [1,4,1,3,3] значение val = 4 уже стоит правильно: фаза 1 спускает на лист значение ребёнка, фаза 2 немедленно останавливается, и val возвращается на место. На случайных данных экономится около четверти сравнений.

Сложность. [math]\displaystyle{ O(\log n) }[/math]; число сравнений примерно [math]\displaystyle{ 1.5\,n\log_2 n }[/math] против [math]\displaystyle{ 2\,n\log_2 n }[/math] у обычного heapsort (подтверждается подсчётом, см. «Служебное»).

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

Операция	Лучший	Средний	Худший	Память
`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{ O(\log n) }[/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]

Оговорка: 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(0, end)	Массив	Хвост
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

Инвариант цикла. a[0..end-1] — куча, a[end..n-1] отсортирован и содержит [math]\displaystyle{ n-end }[/math] наибольших элементов. База — после build-heap. Шаг: a[0] — максимум кучи, то есть максимум среди a[0..end]; после обмена он оказывается в a[end], а a[end..n-1] остаётся отсортированным (он был больше по индукции, а новый элемент — максимум оставшихся). Sift-down восстанавливает кучу в a[0..end-1]. По завершении end = 0, весь массив отсортирован. [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]	нет	отличная

Рис. 6. Heapsort даёт гарантию без лишней памяти; проигрывает по кэшу и устойчивости.

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

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

Очереди с приоритетом. Двоичная куча — основа std::priority_queue, heapq (Python), PriorityQueue (Java); вставка/извлечение — [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 наибольших». Куча размера [math]\displaystyle{ k }[/math] находит [math]\displaystyle{ k }[/math] наибольших элементов за [math]\displaystyle{ O(n\log k) }[/math]; nlargest/nsmallest в Python и «top-k» в потоковой обработке [4].

Алгоритмы на графах. Дейкстра и Прим на двоичной куче дают [math]\displaystyle{ O((n+m)\log n) }[/math]; Хаффман строит префиксный код на мини-куче. Почему: нужна повторяющаяся выборка минимума среди меняющегося множества [1][5].

Приоритетные планировщики. Обработка событий по времени, таймеры, арбитраж задач — всё, где нужен «ближайший» элемент; куча даёт логарифмические операции вставки/извлечения [5].

Рис. 7. Куча и heapsort: приоритетные очереди, in-place сортировка, 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 (сортировка и поиск) [6].

Связанные улучшения: «слабые кучи» (weak heaps) и smoothsort Э. Дейкстры (1981), а также фибоначчиевы и биномиальные кучи (Фредман и Тарьян, 1987 и ранее) для быстрого слияния и decrease-key — см. Фибоначчиева куча, Биномиальная куча [1][7]. Название «пирамидальная сортировка» — русский перевод английского 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 неустойчив (обмен корня с последним меняет порядок равных).
Ошибка в 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 и измерьте экономию сравнений (ожидается ~25%). Подсказка: две фазы, «дырка» в листе.

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.

Поиск

Навигация

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

Содержание

TL;DR

Определения

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

Устройство

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Источники