Пирамидальная сортировка. Лекция 8

Джоном Уильямсом в 1964, а затем улучшена Робертом Флойдом.

В сортировке прямым выбором наименьший элемент на рассматриваемом участке массива фактически отыскивается путём полного просмотра участка, то есть также как в процедуре линейного поиска.

Идея улучшения этой сортировки состоит в переходе от линейного выбора со сложностью O(N) к выбору в дереве, с помощью которого можно сохранить и использовать гораздо больше информации о процессе выбора и уменьшить сложность до O(log2N).

Замечание. Указанные выше оценки сложности относятся не ко всей сортировке в целом, а только к одному из её этапов ― выбору наименьшего на некотором участке массива.

какому-либо виду спорта (шахматы, теннис и т.д.) среди восьми участников. Можно провести чемпионат, когда каждый из участников встречается с каждым, но это требует много времени и затрат.

Есть более простой и быстрый способ организации соревнований -кубковая система. Участников по какому-либо принципу разделяют на пары. Победитель каждой пары выходит в следующий круг, а проигравший выбывает из соревнования.

Однако, кубковая система с выбыванием имеет недостаток: сложно определить второго, третьего и т.д. по силе игрока, в то время как чемпионат распределяет всех по своим местам.

не обязательно второй по силам участник соревнований.

Борисов

Волков

Тютерев

Щуров

Сивашов

Искольный

Шакиров

Бородулин

Борисов

Шакиров

Сивашов

Тютерев

Шакиров

Сивашов

Шакиров

Щуров

Борисов

Сильнее Сивашова может быть Борисов,

сильнее может быть и Щуров, которые

Чтобы выявить второго по силе нужно пройти по дереву соревнования вниз, выбрать соперников Шакирова, организовать между ними матч, а затем победитель сыграет с Сивашовым.

проиграли на ранних этапах Шакирову.

дополнительных матча. Это оказалось возможным за счёт того, что в структуре дерева существует дополнительная информация о выполненных ранее сравнениях и её использование приведет к уменьшению количества сравнений для выбора второго участника

Однако построение подобного дерева из массива требует дополнительных затрат памяти, по крайней мере, за счет дублирования одних и тех же элементов на разных уровнях дерева: вместо хранения N элементов нужно хранить 2N-1 элемент, что фактически эквивалентно использованию вспомогательного массива

дерева лежит специальная разновидность бинарного дерева, которую принято называть пирамидальным деревом или просто пирамидой. Иногда такое дерево называют деревом сортировки.

Пирамидальным называется полное бинарное дерево, у которого ключ корня любого поддерева больше (в более общей трактовке не меньше), чем ключи двух его дочерних вершин.

В отличие от дерева поиска ключи дочерних вершин пирамидального дерева считаются неупорядоченными: ключ левой дочерней вершины может быть как больше, так и меньше ключа правой дочерней вершины

требованиям:
узлами дерева являются элементы массива;

дерево является сбалансированным, т.е. все листья имеют глубину k или k – 1, при этом уровень k – 1 полностью заполнен, а уровень k заполнен слева направо, т.е. форма пирамиды имеет приблизительно такой вид:

требованиям:

выполняется "свойство пирамиды":
каждый элемент меньше либо равен родителю,
корнем дерева является максимальный элемент массива

Пример пирамиды, имеющей глубину 4

ее можно хранить прямо в сортируемом массиве

Здесь – массив из n элементов, нумерация от 0 до n-1

?

ее можно хранить прямо в сортируемом массиве
Массив
94, 67, 18, 44, 55, 12, 06, 42

Слева - направо, сверху - вниз

в котором ключ корня любого поддерева меньше (в более общей трактовке не больше), чем ключи двух его дочерних вершин

60

43

70

65

28

45

54

Ключ корня 70 больше, чем ключи двух его дочерних узлов 65 и 60. Ключ левого поддерева 65 больше ключей 28 и 45, также как и ключ правого поддерева 60 больше, чем ключи 54 и 43 их дочерних узлов. Изображённое дерево является пирамидой

и только после полного заполнения предшествующего уровня
Заполненным считается уровень дерева, содержащий максимально возможное количество узлов

60

43

70

65

28

45

54

Частично незаполненным может быть только самый нижний уровень дерева

новых узлов в дерево. Эти номера принято называть индексами узлов пирамидального дерева

60

43

70

65

28

45

54

1

2

3

4

5

6

7

В этой системе нумерации корневой узел всегда имеет индекс 1.
Два его дочерних узла имеют индексы 2 и 3, а, например, дочерние для узла с индексом 3 имеют индексы 6 и 7 и т.д.

(если они есть) всегда имеют индексы 2k и 2k+1. Для узла с индексом m (m≠1) родительский всегда имеет индекс int(m/2).
Эти простые соотношения между индексами родительского и дочерних узлов обеспечивают высокую эффективность адресной арифметики на машинном уровне

С использованием индексов свойство ключей узлов пирамидального дерева можно записать в виде
(x[k] ≥ x[2k]) ⋀ (x[k] ≥ x[2k+1]), k=1, 2, 3,…, int(N/2)

из элементов сортируемого массива
{45, 28, 54, 43, 70, 60, 65} удалось некоторым образом построить рассматриваемое пирамидальное дерево

По основному свойству пирамиды максимальный элемент (70) находится в её корне и имеет индекс 1. При сортировке в порядке возрастания максимальный элемент должен находиться в конце массива, быть последним, поэтому узел с индексом 1 можно поменять местами с последним узлом (43), имеющим индекс 7, после чего исключить его из дальнейшей сортировки

60

43

70

65

28

45

54

1

2

3

4

5

6

7

60

70

43

65

28

45

54

1

2

3

4

5

6

7

корневом узле

Дерево, у которого свойство упорядоченности (x[k] ≥ x[2k]) ⋀ (x[k] ≥ x[2k+1]) выполняется для всех узлов, кроме корневого называется частично упорядоченным пирамидальным деревом

Оказывается, что восстановление пирамидальности выполняется очень простым способом: нужно поменять местами корень и больший из его двух дочерних узлов, а затем рекурсивно применить эту процедуру к выбранному поддереву

60

70

65

43

28

45

54

1

2

3

4

5

6

7

60

70

65

45

28

43

54

1

2

3

4

5

6

7

В результате такого преобразования вновь получится пирамидальное дерево, в корне которого находится максимальный ключ

который теперь можно присоединить к уже упорядоченной части, поменяв местами с предпоследним элементом

60

70

54

45

28

43

65

1

2

3

4

5

6

7

Вновь получено частично упорядоченное пирамидальное дерево, которое можно тем же способом преобразовать в пирамидальное

54

70

60

45

43

65

1

2

3

5

6

7

28

Этот процесс следует продолжать до тех пор, пока все элементы массива не окажутся на своих местах

4

для применения этого способа нужно уметь представлять сортируемый массив в виде пирамидального дерева

В принципе, для начального построения дерева из заданного сортируемого массива применяется практически тот же самый подход, что и для восстановления дерева

Вначале из заданного массива, исходя из соответствия индексов массива индексам узлов пирамидального дерева, строится дерево, в котором условие пирамидальности ещё не выполняется

2, 16, 9, 10, 14, 8, 7}. Элементы по одному выбираем из массива и включаем в пирамидальное дерево в соответствии с правилами его заполнения, не обращая при этом внимания на значения элементов

4 1 3 2 16 9 10 14 8 7

1 2 3 4 5 6 7 8 9 10

Массив

Индексы

4

1

7

10

1

2

3

3

2

4

16

5

9

6

10

7

14

8

8

9

Построение пирамиды

Получилось бинарное дерево общего вида, ключи узлов которого являются соответствующими элементами сортируемого массива

Это дерево не является пирамидальным, но его довольно просто можно преобразовать в пирамидальное

образуют нижний уровень дерева, его нижний слой

По построению дерева количество листьев всегда равно N-int(N/2). Причём в массиве они занимают последние позиции: x[i], i=int(N/2)+1,…,N

Процедура преобразования полученного дерева сводится к последовательному перебору в обратном порядке всех ещё не упорядоченных узлов (в рассматриваемом примере узлов с индексами
5, 4, …,1) и применению описанного выше приёма приведения частично упорядоченного дерева к пирамидальному, к совокупности узлов, состоящей из вновь рассматриваемого и уже пирамидальных

Итак, выбираем узел с индексом 5 и преобразуем поддерево в корне которого он находится , так чтобы выполнялось свойство пирамидальности

16

которого меньше, чем у узла 5, можно утверждать, что поддерево с корнем 16 уже является пирамидальным

Следующим по порядку рассматривается узел с индексом 4

2

Он имеет два дочерних с ключами 8 и 14. Большим из них является узел с ключом 14 и его нужно поменять местами с корневым

Следующим по порядку рассматривается узел с индексом 3

3

Он имеет два дочерних с ключами 9 и 10. Большим из них является узел с ключом 10 и его нужно поменять местами с корневым

14 и 16
Больший из них 16 должен поменяться местами с корневым узлом

Но такой обмен нарушил свойство пирамидальности для поддерева, имеющего в качестве корня узел с индексом 5

Следовательно, нужно восстановить пирамидальность, выполнив обмен для нового корня и его дочернего узла с индексом 10

с большим дочерним (16)

Теперь работаем в поддереве с узлом, имеющим индекс 2. Его нужно поменять местами с большим дочерним (14)

И последним преобразуется поддерево, имеющее корнем узел с индексом 4. Он меняется местами с дочерним узлом, с индексом 9

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

Заметим, что это пирамидальное дерево эквивалентно массиву
{16, 14, 10, 8, 7, 9, 3, 2, 4, 1}, он существенно отличается от исходного
{4, 1, 3, 2, 16, 9, 10, 14, 8, 7}

1

И алгоритм построения пирамидального дерева и последующее его преобразование сводятся к перемещениям соответствующих элементов в сортируемом массиве

Сводя все предыдущие рассуждения вместе получим следующий алгоритм пирамидальной сортировки:

Вначале нужно преобразовать сортируемый массив к виду, эквивалентному пирамидальному дереву. В результате на первое место попадет максимальный по всему массиву элемент x[1]=max {x[i], i=1,2,…, N}

местами находящийся на первом месте максимальный и N элементы. После чего последний элемент образует уже упорядоченную часть, а элементы с 1-го по N-1-й ― неупорядоченную
Получившаяся совокупность элементов неупорядоченной части массива эквивалента частично упорядоченному пирамидальному дереву, которое восстанавливается до полностью пирамидального. При этом максимальный из неупорядоченной части вновь попадает в начало массива

чего на «своих» местах уже находятся N-1-й и N-й элементы, образуя упорядоченную часть
Первые N-2 элемента, образующие неупорядоченную часть, вновь преобразуются и максимальный из них перемещается на первое место

максимальный элемент x[1] меняется местами с последним элементом неупорядоченной части x[N-i+1]
Затем, из уменьшенной на один элемент неупорядоченной части при восстановлении её пирамидальности выбирается наибольший и перемещается на первое место в массиве

как и все улучшенные варианты сортировок) не рекомендуется применять для небольших массивов, так как, например, для N=1000 даже прямые вставки окажутся примерно вдвое быстрее пирамидальной

Сравнение пирамидальной сортировки и сортировки Шелла показывает, что для малых и средних N более эффективна сортировка Шелла. По мере роста N пирамидальная сортировка начинает работать быстрее сортировки Шелла

Следует обратить внимание на то, что пирамидальная сортировка даже в худших случаях имеет сложность O(N*log2N). В то время как у сортировки Шелла оценка O(N1,2) получена для среднего, а не для худшего случая. В худшем случае у Шелла O(N2)

Строго говоря сложность как раз и рассматривается только в худшем случае. Поэтому O(N1,2) не может называться сложностью процедуры Шелла