Пирамидальная сортировка (heap sort) — это разновидность турнирной сортировки.
Дан массив из N целых чисел. Необходимо упорядочить его элементы (обменивая их местами) в порядке неубывания (нестрогого возрастания) методом турнирной сортировки.
Первый этап. Построение кучи
На первом этапе алгоритма элементы массива расставляются таким образом, чтобы образовать так называемую кучу (пирамиду) — дерево в массиве, где у i-го элемента есть два дочерних элемента с индексами 2i + 1 и 2i + 2 (если соответствующие индексы находятся в рамках массива). На дочерние элементы накладывается ограничение, состоящее в том, чтобы их значения были не больше значения родительского элемента.
m[i] ≥ m[2i + 1]
m[i] ≥ m[2i + 2]
Коль скоро в начале процесса элементы расположены вовсе не так, делаем следующее
(замечая однако, что все элементы, начиная с m[N DIV 2], если их рассматривать как родительские, удовлетворяют свойству пирамиды, т. к. для них в массиве нет детей):
Перебираем элементы массива справа налево, начиная с (N DIV 2 - 1).
Для каждого элемента (назовём его индекс i) выполняем процедуру просеивания.
Процедура просеивания Sift (дан номер элемента k и длина массива n):
1) Выбираем большего из сыновей k. Пусть индекс большего сына = j.
(таким образом,либо j = 2k + 1, либо j = 2k + 2)
2) Если m[j] > m[k], то меняем их местами.
3) k := j
4) Перейти к шагу 2. Цикл закончить, когда k выйдет за рамки
левой половины массива (т. к. это значит, что у k нет сыновей).
При выборе большего сына надо иметь в виду, что второй из них может не существовать. Длину массива считать за n.
Второй этап. Собственно сортировка
Куча получилась. А значит, элемент m[0] — наибольший.
Пусть n = N.
Элементы с n до N - 1 — отсортированная часть массива, а
n — количество элементов, которое осталось поместить на своё место.
Пока n # 0 делаем:
1) Меняем местами m[0] и m[n - 1].
2) Элемент m[n - 1] встал на своё место. Уменьшаем n на единицу.
3) Возможно, m[0] теперь нарушает свойство пирамиды. Просеиваем 0-й элемент, но так, чтобы не была затронута часть массива, начиная с элемента под номером n (соответствующая процедура уже готова).
Массив упорядочен.
Литература:
Н. В. Вирт. Алгоритмы и структуры данных (2010). С. 83.
9 января 2023 г.
г. Рига, ЛССР