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

Пирамидальная сортировка (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 г.
г. Рига, ЛССР