4. Якщо A[i] - вузол дерева та i > 1, то A[i mod 2] - вузол - “батько” вузла A[i];

Вхідні – вихідні дані

Для роботи з даною програмою та алгоритму пірамідального сортування взагалі, нам необхідно ввести елементи масиву визначеної довжини, який необхідно відсортувати.

В результаті роботи програми ми отримаємо відсортований масив введених елементів.

Вхідні дані	Вихідні дані
Розмір вхідного масиву «N» Масив з «N» елементів, елементи – цілі числа ( Масив A[1..N] – невпорядкований ).	Впорядкований масив з «N» елементів, елементи – цілі числа , кожен елемент масиву більше або дорівнює попередньому (Масив A[1..N] ; A[i]<= A[i+1]).

Математичний розв’язок

Алгоритм пірамідального сортування працює в два етапи:

I. Побудова сортуючого дерева;

II. Просіювання елементів по сортуючому дереву.

Як на I-ому, так і на II-ому етапах елементарна дія алгоритму полягає в вирішенні сімейного конфлікту: якщо найбільший із синів більше, ніж батько, то переставляються батько і цей син (процедура Swap).

У результаті перестановки може виникнути новий конфлікт у тому трикутнику, куди переставлений батько. У такий спосіб можна говорити про конфлікт (роду) у піддереві з коренем у вершині i. Конфлікт роду вирішується послідовним вирішенням сімейних конфліктів проходом по дереву вниз. Конфлікт роду вирішено, якщо прохід закінчився (i > n div 2), або ж в результаті перестановки не виник новий сімейний конфлікт (процедура Conflict).

I етап – побудова сортуючого дерева - оформимо у виді рекурсивної процедури, використовуючи визначення:

Якщо ліве і праве піддерева ( T[2i] і T[2i+1] ) дерева T[i] є сортуючими, то для перебудови T[i] необхідно вирішити конфлікт роду в цьому дереві.

II етап - етап просіювання - для k від n до 2 повторюються наступні дії:

1.Переставити A[1] і A[k];

2.Побудувати сортуюче дерево початкового відрізка масиву A[1..k-1], усунувши конфлікт роду в корені A[1]. Відзначимо, що 2-а дія вимагає введення в процедуру Conflict параметра k.

Нескладно підрахувати, що С(n) = O( n log2 n ), М(n) = O( n log2 n )

Схема алгоритму програми

Алгоритм процедури введення даних

Алгоритм процедури виведення результатів сортування

Алгоритм процедури побудови дерева

Алгоритм процедури перестановки елементів

b = a[i]

a[i] = a[j]

a[j] = b

Алгоритм процедури «вирішення сімейного конфлікту»