Алгоритмпірамідального сортування (HeapSort) - Студопедія
У деяких додатках (наприклад, у завданнях управління обладнанням у реальному часі) дуже важливо мати гарантію, що час роботи критичних гілок програми навіть у найгіршому разі не перевищить певної заданої величини. Для таких завдань використання QuickSort може виявитися неприйнятним з огляду на названий вище недолік цього алгоритму – час роботи порядку O(n 2 ) у гіршому випадку. У цій ситуації слід використовувати такий алгоритм, який працює гарантовано швидко навіть у найгіршому випадку.
Найбільш відомим з таких алгоритмів є HeapSort, який українською мовою прийнято називати пірамідальним сортуванням.
В основі алгоритму лежить поняття піраміди.
Масив A називається пірамідою, якщо для всіх його елементів виконані такі нерівності:
(3.1)
Сенс нерівностей (3.1) можна наочно пояснити на рис. 3.1.
Мал. 3.1. Подання піраміди у вигляді дерева
На малюнку масив-піраміда з 10 елементів зображено у вигляді збалансованого бінарного дерева, вершини якого пронумеровані зверху донизу та зліва направо. При цьому елемент ak завжди буде в дереві «батьком» елементів a2k і a2k+1 (якщо такі елементи є). Тоді нерівності (3.1) означають, що значення «батька» має бути не меншим, ніж значення кожного з «синів».
Слід пам'ятати, що піраміда – це дерево, а масив з певними властивостями, а зображення піраміди як дерева дано лише наочності.
Піраміда зовсім не обов'язково є сортованим масивом, проте вона є зручним проміжним результатом при сортуванні. Зазначимо, перший елемент піраміди (a1) завжди є максимальним елементом масиву.
Роботаалгоритм HeapSort складається з двох послідовних фаз. На першій фазі вихідний масив перебудовується в піраміду, але в другій фазі з піраміди будується сортований масив.
Основною операцією, яка використовується як на першій, так і на другій фазах сортування, є так зване просіювання елемента крізь піраміду.
Припустимо, що нерівності (3.1) виконані елементів піраміди, починаючи з індексу k+1 (тобто елементів ak+1, ak+2, … , an). Процедура просіювання елемента ak повинна забезпечити виконання (3.1) для ak і при цьому не порушити цих нерівностей ak+1, ak+2, … , an.
Алгоритм просіювання полягає в наступному.
1. Якщо немає синів (тобто. 2k > n), то просіювання закінчено.
2. Якщо має рівно одного сина (тобто 2k = n), то присвоїти l := n і перейти до кроку 4.
3. Порівняти значення двох синів вершини ak: якщо a2k & gt; a2k+1, то l := 2k, інакше l := 2k + 1 (тобто l – це індекс більшого із синів ak).
4. Порівняти значення елемента ak із значенням його більшого сина al: якщо ak
4. Якщо n > 1, то перейти до кроку 1, інакше сортування завершено.
На кожній ітерації другої фази відбувається виняток з піраміди максимального з елементів, що залишилися в ній. Цей елемент записується на належне місце в сортованому масиві. До кінця роботи алгоритму вся піраміда перетворюється на сортований масив.
Оцінимо час роботи кожної фази алгоритму HeapSort. Перша фаза складається з n/2 операцій просіювання, кожна з яких включає трохи більше log2(n) ітерацій циклу. Звідси можемо легко отримати першої фази оцінку Tмакс(n) = O(n×log(n)). Однак ця оцінка надто груба. Надалі нам знадобиться точніша оцінка часу роботи першої фази HeapSort. Щоб отриматиТаку оцінку, розглянемо рис. 3.2.
Мал. 3.2. Число ітерацій просіювання при побудові піраміди
З-поміж усіх n елементів масиву A приблизно половина (n/2) не має синів і не вимагає просіювання (тобто число ітерацій просіювання дорівнює 0). Чверть елементів (n/4) має синів, але не має онуків, для цих елементів може бути виконано не більше однієї ітерації просіювання. Для однієї восьмої частини елементів (n/8) можуть бути виконані дві ітерації, для однієї шістнадцятої (n/16) три ітерації і т.д. Сумарна кількість ітерацій просіювання визначиться формулою: n (0×1/2 + 1×1/4 + 2×1/8 + 3×1/16 + …). Тряхнувши спогадами про матаналіз, можна обчислити значення суми ряду в дужках; це значення дорівнює 1. Отже, отримуємо лінійну оцінку часу першої фази: Tмакс(n) = O(n).
Друга фаза алгоритму в основному являє собою просіювання елементів крізь піраміду, що зменшується. Число ітерацій циклу можна приблизно оцінити як суму log2(n) + log2(n–1) + log2(n–2) + … + log2(3) + log2(3). Повіримо без доказу, що з точністю до O-великого ця сума дає Tмакс(n) = O(n×log(n)).
Час роботи алгоритму загалом визначається більш трудомісткою другий фазою і задовольняє оцінці Tмакс(n) = O(n×log(n)). Можна довести, що така оцінка справедлива й у середнього часу сортування: Tср(n) = O(n×log(n)). Таким чином, HeapSort є алгоритмом сортування, який гарантує досить швидку роботу навіть у разі найневдаліших вихідних даних. Цим HeapSort вигідно відрізняється від QuickSort, який такої гарантії не дає. З іншого боку, практика показує, що в середньому алгоритм HeapSort працює приблизно вдвічі повільніше за QuickSort.
Чи не знайшли те, що шукали? Скористайтеся пошуком: