Пірамідальне сортування

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

Нехай є вихідний масив n елементів а1 а2 а3, . . ., аn. Розташуємо ці елементи у вигляді двійкового дерева наступного виду (тут важливий порядок дотримання індексів елементів):

Подібне дерево називається пірамідою, якщо для всіх елементів з індексами від 1 до n/2 виконуються такі умови:

Такі піраміди іноді називаютьмінімальними, на відміну від максимальних, де правило впорядкованості прямо протилежне.

З прикладу видно, що піраміда НЕ дерево пошуку, т.к. будується за іншими правилами.

Можна відзначити наступнікорисні властивості піраміди:

• навершині піраміди завжди знаходитьсянайменший елемент у всьому масиві (елемент а1), елемент а2 є найменшим для лівого піддерева, елемент а3 є найменшим для правого піддерева і т.д.
• вершини, що лежать на нижньому рівні пірамідизавжди утворюють із себе елементарні піраміди, оскільки у них немає ніяких нащадків і їх порівнювати ні з ким

Пірамідальне сортування включає два великі етапи:

• подання вихідного масиву у вигляді піраміди
• послідовні видалення мінімального елемента з вершини піраміди із заміною його іншим елементом

Реалізація 1 етапу включає наступні кроки:

• умовно поділяємо вихідний масив на дві половини: ліву з індексами від 1 до [n/2], і праву з індексами від [n/2]+1 до n (тут [ ] означає цілу частину); вважаємо поки, що ліва половина утворює верхню частину піраміди, що будується, а права - нижній шар термінальних вершин
• вибираємо у лівій половині останній елемент (його індекс m=[n/2]), а правій половині – його безпосередніх нащадків (одного чи двох, але хоча б один буде обов'язково) з індексом 2m і, можливо, 2m+1
• якщо нащадків два, то вибираємо з них найменшого
• порівнюємо елемент аm з найменшим із нащадків: якщо він більший, то міняємо ці елементи в масиві місцями для отримання фрагмента піраміди; в іншому випадку залишаємо все без змін, оскільки ці елементи вже утворюють фрагмент піраміди
• повторюємо всі описані дії послідовно для решти елементів праворуч наліво, тобто. для AM-1, AM-2, AM-3, . . ., а1, причому якщо відбувається обмін між батьківською вершиною і одним з нащадків, виконується перевірка для нової вершини-нащадка, т.к. вона може мати своїх нащадків, з якими можливо буде потрібно її обміняти на виконання умови піраміди.

Тим самим, для кожного елемента масиву знаходиться його нове розташування масиві таким чином, щоб виконувались умови піраміди. Процес визначення потрібного положення елемента в масиві-піраміді називаютьпросіюванням елемента через піраміду. Побудова піраміди закінчується після просіювання першого елемента а1.Приклад для 15 елементів наведено в таблиці (символ

---