методу, розглянемо перевернуту сортування вибором. Під час проходу, замість вставки найменшого елемента в лівий кінець масиву, будемо вибирати найбільший елемент, а готову послідовність будувати в правому кінці.
55 12 42 94 18 06 67 вихідний масив
55 12 42 67 18 06 | 94 94 lt; - gt; 67
55 12 42 06 18 | 67 94 67 lt; - gt; 06
+18 12 42 06 | 55 67 94 55 lt; - gt; 18
+18 12 42 | 44 55 67 94 44 lt; - gt; 06
18 грудня | 42 44 55 67 94 42 lt; - gt; 42
12 | 18 42 44 55 67 94 18 lt; - gt; 12
| 12 18 42 44 55 67 94 12 lt; - gt; 12
Малюнок 2. Приклад дії масиву а [0] ... a [7]
Вертикальною рисою відзначена ліва межа вже відсортованої (правої) частини масиву. Розглянемо оцінку кількості операцій докладніше. Всього виконується n кроків, кожен з яких складається у виборі найбільшого елемента з послідовності a [0] ... a [i] і надалі обміні. Вибір відбувається послідовним перебором елементів послідовності тому необхідне на нього час: O (n). Отже, n кроків по О (n) кожен - це О).
Зробимо удосконалення: побудуємо структуру даних, що дозволяють вибирати максимальний елемент послідовності нема за O (n), а за O (logn) часу. Тоді загальну швидкодію сортування буде n * O (logn)=O (n log n).
Ця структура також повинна дозволяти швидко вставляти нові елементи (щоб швидко її побудувати з вихідного масиву) і видаляти максимальний елемент (він буде міститися у вже відсортовану частину масиву - його правий кінець).
Отже назвемо пірамідою бінарне дерево висоти k, в якому:
· всі вузли мають глибину k або k - 1 - дерево збалансоване.
· при цьому рівень повністю заповнений, а рівень k заповнений зліва направо.
· виконується властивість піраміди: кожен елемент менше, або дорівнює батьку.
Відповідність між геометричною структурою піраміди як дерева і масивом встановлюється за такою схемою на малюнку 3.
· в а [0] зберігається корінь дерева
· лівий і правий сини елемента a [i] зберігаються, відповідно, в a [2i + 1 і a [2i + 2]
Таким чином, для масиву, що зберігає в собі піраміду, виконується наступне характеристичне властивість: a [i] gt;=a [2i + 1] і a [i] gt;=a [2i + 2 ]
Плюси такого зберігання піраміди очевидні:
· ніяких додаткових змінних, потрібно лише розуміти схему
· вузли зберігаються від вершини і далі вниз, рівень за рівнем.
· вузли одного рівня зберігаються в масиві зліва направо
Запишемо у вигляді масиву піраміду, зображену вище. Зліва-направо, зверху-вниз: 94 67 18 44 55 12 06 42. На малюнку 3 місце елемента піраміди в масиві позначено цифрою праворуч-вгорі від нього.
Відновити піраміду з масиву як геометричний об'єкт легко - досить згадати схему зберігання і намалювати, починаючи від кореня.
Почати побудова піраміди можна з a [k] ... a [n], k=[size/2]. Ця частина масиву задовольняє властивості піраміди, так як не існує індексів i, j: i=2i + 1 (або j=2i + 2). Такі i, j перебувають за кордоном масиву.
Далі будемо розширювати частина масиву, що володіє настільки корисною властивістю, додаючи по одному елементу за крок. Наступний елемент на кожному кроці додавання - той, який стоїть перед вже готової частиною.
Щоб при додаванні елемента зберігалася пірамідальність, будемо використовувати наступну процедуру розширення піраміди a [i + 1] .. a [n] на елемент a [i] вліво.
Новий елемент буде просівати крізь піраміду.
Нижче дана ілюстрація процесу для піраміди з 8-ми елементів:
55 12 42//94 18 червня 67
55 12//67 94 18 06 42
55//18 67 94 +12 06 42
//94 18 67 55 12 06 42
//94 67 18 44 55 12 06 42
Праворуч - частина масиву, яка задовольняє властивості піраміди, інші елементи додаються один за іншим, справа наліво.
У геометричній інтерпретації ключі з початкового відрізка a [size/2] ... a [n] є листям в бінарному дереві, як зображено нижче. Один за іншим інші елементи просуваються на свої місця, і так - поки не буде побудована вся піраміда.
неготовими частина піраміди (початок масиву) пофарбована в білий колір, що задовольняє властивості піраміди кінець масиву - у темний.
...
