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

Идея

Двоичная max-куча (пирамида) — это массив, который рассматривается как полное двоичное дерево: дети A[i] — это A[2i + 1] и A[2i + 2], и каждый родитель не меньше своих детей. Поэтому наибольший элемент всегда в корне A[0].

1. Строим кучу из массива.
2. Меняем корень (максимум) с последним элементом кучи — максимум теперь на своём окончательном месте. Уменьшаем кучу на один и просеиваем вниз новый корень, чтобы восстановить свойство кучи.
3. Повторяем, пока куча не опустеет.

Пример

Сортируем [5, 2, 4, 6, 1, 3].

1. Строим max-кучу — просеиваем вниз каждого родителя, от последнего к корню:

      5                5                6
    /   \            /   \            /   \
   2     4    →     6     4    →     5     4
  / \   /          / \   /          / \   /
 6   1 3          2   1 3          2   1 3

Куча в виде массива: 6, 5, 4, 2, 1, 3.

2. Раз за разом извлекаем максимум. Отсортированный хвост выделен жирным:

Шаг	Обмен корня с последним	После просеивания
1	3, 5, 4, 2, 1, 6	5, 3, 4, 2, 1, 6
2	1, 3, 4, 2, 5, 6	4, 3, 1, 2, 5, 6
3	2, 3, 1, 4, 5, 6	3, 2, 1, 4, 5, 6
4	1, 2, 3, 4, 5, 6	2, 1, 3, 4, 5, 6
5	1, 2, 3, 4, 5, 6	1, 2, 3, 4, 5, 6

Попробуйте сами

Тот же пример по шагам. Измените данные или нажмите «Старт».

Псевдокод

HEAP-SORT(A)
  for i = ⌊n / 2⌋ − 1 downto 0          // строим кучу
    SIFT-DOWN(A, i, n)
  for end = n − 1 downto 1
    swap A[0] and A[end]
    SIFT-DOWN(A, 0, end)

SIFT-DOWN(A, i, size)                   // куча — это A[0..size − 1]
  loop
    largest = i
    l = 2i + 1, r = 2i + 2
    if l < size and A[l] > A[largest]: largest = l
    if r < size and A[r] > A[largest]: largest = r
    if largest = i: return
    swap A[i] and A[largest]
    i = largest

Сложность

Лучший	Средний	Худший	Память	Устойчивая	На месте
O(n log n)	O(n log n)	O(n log n)	O(1)	нет	да

• Построение кучи занимает всего O(n), а не O(n log n): большинство узлов внизу и просеиваются лишь на несколько уровней ($\sum _h\frac{n}{2^{h+1}}\cdot h=O(n)$).
• Каждое из n − 1 извлечений просеивает не больше чем через ${\log }_{2}n$ уровней: всего O(n log n), на любых данных.
• Память O(1): куча живёт в самом массиве.
• Неустойчивая: обмен корня с последним элементом уносит элементы далеко.

Когда применять

Когда нужны гарантированные O(n log n) без дополнительной памяти. На практике медленнее быстрой сортировки, потому что прыгает по массиву (плохая локальность кэша). Та же куча — основа очереди с приоритетом.

Использование

import { heapSort } from 'ts-ds';

const array = [5, 2, 4, 6, 1, 3];
heapSort(array);

Справочник API

Литература

• J. W. J. Williams. «Algorithm 232: Heapsort». Communications of the ACM 7(6), 1964.
• Кормен, глава 6 «Пирамидальная сортировка».
• Седжвик, Алгоритмы, §2.4 «Очереди с приоритетами».