Материал: Інформатика_1 (методи побудови алгоритмівта та їх аналіз)

Мал. 64

171

_@©@

^@©@

Мал. 65

Мал. 67

12)

^@©@@@@

Мал. 68

172

^{@©@@@@@ @©@@@@@©}

Мал. 69

А тепер перейдемо до узагальнення всього вищесказаного.

Метод, що базується на описаному вище алгоритмі, нази-ваеться HeapSort.

Подивимося на загальний вигляд бінарного дерева як на піраміду (мал. 70).

Мал. 70

Аналізуючи малюнок 70, неважно помітити таку закономір-ність:

h_i>h_2lTah_l>h_{2l + v}Rei = 1, 2, ..., [л/2].

3 малюнка 70 видно, що термінальними вершинами є ті, по­рядков! номери яких у масиві більші за [л/2]. Усім іншим еле-ментам масиву в бінарному дереві відповідають вершини, які мають нащадків. Тому згідно з нашим алгоритмом будувати піраміду треба для елементів масиву з індексами і - [л/2], [л/2] - 1,..., 2, 1. Саме в такій послідовності треба переглядати елементи масиву на кожному етапі, включати їх у бінарне дере­во і будувати одночасно піраміду.

Визначаючи дерево як піраміду, слід констатувати, що Aj = max (л,, h₂,..., h_n). Але аналогічно елемент h₂ є найбільшим для свого піддерева, а л₃ - для свого. А це означав, що при ви-лученні (згідно з нашим алгоритмом) для наступного перегля­ду найбільшого елемента масиву, який знаходиться в корені побудованої піраміди, для подальшого збереження властивос-тей піраміди в бінарному дереві кількість переставлень якщо не зменшуеться, то явно не збільшується.

Отже, підіб'ємо підсумок наших міркувань у вигляді словесно­го алгоритму. Фактично цей алгоритм складається з двох кроків:

173

• побудувати піраміду для тієї частини масиву, яка розгля-дається на даному кроці;

• поміняти місцями найбільший елемент, який знаходиться в корені дерева, з останнім елементом тієї частини масиву, що розглядається, та зменшити з кінця кількість елементів маси­ву, частина якого розглядається.

Реалізуємо цей алгоритм мовою програмування Pascal.

Спершу розглянемо процедуру, яка реалізує переміщення поточного L-го елемента масиву на свое місце в піраміді. Це здійснюється шляхом порівняння його значения зі значениями безпосередніх нащадків. Якщо серед нащадків є більший за по-точний елемент, то піднімаємо його на місце поточного і визна-чаємо цього нащадка поточним елементом. Процес завер-шується в одному з таких двох випадків: або ми дійшли до тер-мінальної вершини, або обидва нащадки менші за поточний елемент. Отже, процедура pyramida будує піраміду з елементів масиву a_L, ..., a_R.

procedure pyramida (L, R: word); var i, j: word; x: word;

begin {Запам'ятовуємо значения вершини,)

X := а[Ц; {яке необхідно поставити на свое місце в піраміді.)

i := L; {Визначаємо цю вершину поточною.)

j := 2 * L; {Визначаємо лівого нащадка для поточної вершини.)

{Якщо існує правий нащадок для поточноі вершини)

if (j<R) and (a[j + 1] > a[j]) {i він більшийзалівого,)

then j := j + 1; {то переходимо до нього.)

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

while (j <= R) and (a[j] > x) do

begin

{Якщо нащадок більший за поточний елемент,)

a[i] := a[j]; {то переміщаємо його на місце поточного.)

І := j; {Переходимо до нащадка як до поточного елемента.)

j := 2 * j; {Визначаємо для поточного елемента його нащадка.)

{Якщо існує правий нащадок для поточно! вершини)

if (j<R) and (a[j + 1] >a[j]) {i він більший за лівого,)

then j := j + 1 {то переходимо до нього.)

end;

а[І] := X {Ha місце поточно! вершини записуємо значення елемента а[Ц.)

end;

Тепер основна частина алгоритму виглядатиме так:

L := (n div 2) + 1; R := п; {Визначимо термінальні вершини.)

{Формування стартової піраміди із заданих п елементів масиву.) while L > 1 do begin

L := L - 1; {Переміщення L від (n div 2) + 1 до 1.)

{Включения кожного L-го елемента масиву в піраміду.) pyramida (L, R) end;

174

while R > 1 do {Перегляд фрагментів масивуа[1] a[R].)

begin

x:=a[1]; a[1] :=a[R]; a[R] :=x; {Обмінмісцямиелементіва[і]іа[Я].} R := R - 1; {Зменшення довжини масиву з кінця.} pyramida (1, R) {Побудова піраміди для фрагментів масиву а[1] а[Я].}

end;

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

Раніше зазначалося, що даний алгоритм складається з двох частин: побудова піраміди для фрагмента масиву та вилучення найбільшого елемента, який з'явився у корені бінарного дерева.

Із цих міркувань можна визначити оцінку ефективності ви-користання методу пірамідального сортування. Рух по бінарно-му дереву будь-якого елемента для побудови піраміди стано-вить 0(log₂n). Але оскільки цю процедуру треба виконати для всіх п елементів масиву, то остаточна оцінка даного методу ста-новить 0(п log₂n).

Оскільки метод пірамідального сортування належить до удосконалених методів, то результати його тестування повин-ні відповідно це продемонструвати. Рекомендується підібрати такі вхідні дані:

• вхідний масив уже впорядкований необхідним чином;

• вхідний масив є частково впорядкованим;

• вхідний масив упорядкований у зворотному порядку;

• елементи вхідного масиву розміщені випадковим чином. При тестуванні передбачити п = 10, п = 100, п = 1000,

п = 10 000, п = 30 000.

/ Запитання для самоконтролю

1. На якому методі прямого сортування базується метод піра-мідапьного сортування?

2. Зобразіть одновимірний масив у вигляді бінарного дерева, ви-користавши для цього власний приклад.

3. Як виглядатиме бінарне дерево, побудоване з того самого масиву, що й у запитанні 2, але після його упорядкування за спаданиям?

4. Які характерні ознаки можна відмітити, порівнюючи бінарні де­рева у запитаннях 2-3?

5. Яке бінарне дерево можна називати пірамідою, або бінарною купою?

6. Що можна сказати про значения елемента, який знаходиться в корені піраміди?

7. Продемонструйте на власному прикладі перетворення будь-якого бінарного дерева на піраміду, зобразивши цю інформацію як у вигляді дерева, так і у вигляді масиву.