Отже, ми поступово переходимо від більш-менш простих до складних, але ефективних методів. Пірамідальна сортування є першим з розглянутих методів, швидкодія яких оцінюється як O (n log n).
Як деякої прелюдії до основного методу, розглянемо перевернуту сортування вибором. Під час проходу, замість вставки найменшого елемента в лівий кінець масиву, будемо вибирати найбільший елемент, а готову послідовність будувати в правому кінці.
Приклад дій для масиву a [0]. a [7]:
Вертикальної рисою відзначена ліва межа вже відсортованої (правої) частини масиву.
Розглянемо оцінку кількості операцій докладніше.
Всього виконується n кроків, кожен з яких складається у виборі найбільшого елемента з послідовності a [0] .. a [i] і надалі обміні. Вибір відбувається послідовним перебором елементів послідовності, тому необхідне на нього час: O (n). Отже, n кроків по O (n) кожен - це O (n 2).
Зробимо удосконалення: побудуємо структуру даних, що дозволяє вибирати максимальний елемент послідовності нема за O (n), а за O (logn) часу. Тоді загальну швидкодію сортування буде n * O (logn) = O (n log n).
Ця структура також повинна дозволяти швидко вставляти нові елементи (щоб швидко її побудувати з вихідного масиву) і видаляти максимальний елемент (він буде міститися в уже відсортовану частину масиву - його правий кінець).
Отже, назвемо пірамідою (Heap) бінарне дерево висоти k, в якому
- всі вузли мають глибину k або k-1 - дерево збалансоване.
- при цьому рівень k-1 повністю заповнений, а рівень k заповнений зліва направо, тобто форма піраміди має приблизно такий вигляд:
- виконується "властивість піраміди": кожен елемент менше, або дорівнює батькові.
Як зберігати піраміду? Найменш клопітно - помістити її в масив.
Відповідність між геометричною структурою піраміди як дерева і масивом встановлюється за такою схемою:
- в a [0] зберігається корінь дерева
- лівий і правий сини елемента a [i] зберігаються, соответственнно, в a [2i + 1] і a [2i + 2]
Таким чином, для масиву, що зберігає в собі піраміду, виконується наступне характеристичне властивість: a [i]> = a [2i + 1] і a [i]> = a [2i + 2].
Плюси такого зберігання піраміди очевидні:
- ніяких додаткових змінних, потрібно лише розуміти схему.
- вузли зберігаються від вершини і далі вниз, рівень за рівнем.
- вузли одного рівня зберігаються в масиві зліва направо.
Запишемо у вигляді масиву піраміду, зображену вище. Зліва-направо, зверху-вниз: 94 67 18 44 55 12 06 42. На малюнку місце елемента піраміди в масиві позначено цифрою праворуч-вгорі від нього.
Відновити піраміду з масиву як геометричний об'єкт легко - достатньо згадати схему зберігання і намалювати, починаючи від кореня.
Фаза 1 сортування: побудова піраміди
Hачать побудова піраміди можна з a [k]. a [n], k = [size / 2]. Ця частина масиву задовольняє властивості піраміди, так як не існує індексів i, j: i = 2i + 1 (або j = 2i + 2). Просто тому, що такі i, j знаходяться за кордоном масиву.
Слід зауважити, що неправильно говорити про те, що a [k] .. a [n] є пірамідою як самостійний масив. Це, взагалі кажучи, не вірно: його елементи можуть бути будь-якими. Властивість піраміди зберігається лише в рамках вихідного, основного масиву a [0]. a [n].
Далі будемо розширювати частина масиву, що володіє настільки корисним властивістю, додаючи по одному елементу за крок. Наступний елемент на кожному кроці додавання - той, який стоїть перед уже готової частиною.
Щоб при додаванні елемента зберігалася пирамидальность, будемо використовувати наступну процедуру розширення піраміди a [i + 1] .. a [n] на елемент a [i] вліво:
- Дивимося на синів зліва і справа - в масиві це a [2i + 1] і a [2i + 2] і вибираємо найбільшого з них.
- Якщо цей елемент більше a [i] - міняємо його з a [i] місцями і йдемо до кроку 2, маючи на увазі нове положення a [i] в масиві. Інакше кінець процедури.
Новий елемент "просівається" крізь піраміду.
З огляду на, що висота піраміди h <= log n, downheap требует O(log n) времени. Полный код процедуры построения пирамиды будет иметь вид:
Нижче дана ілюстрація процесу для піраміди з 8-ї елементів:
У геометричній інтерпретації ключі з початкового відрізка a [size / 2]. a [n] є листям в бінарному дереві, як зображено нижче. Один за іншим інші елементи просуваються на свої місця, і так - поки не буде побудована вся піраміда.
На малюнках нижче зображено процес побудови. Неготова частина піраміди (початок масиву) пофарбована в білий колір, що задовольняє властивості піраміди кінець масиву - в темний.
Фаза 2: власне сортування
Отже, завдання побудови піраміди з масиву успішно вирішена. Як видно з властивостей піраміди, в корені завжди знаходиться максимальний елемент. Звідси випливає алгоритм фази 2:
- Беремо верхній елемент піраміди a [0]. a [n] (перший в масиві) і міняємо з останнім місцями. Тепер "забуваємо" про цей елемент і далі розглядаємо масив a [0]. a [n-1]. Для перетворення його в піраміду досить просіяти лише новий перший елемент.
- Повторюємо крок 1, поки що обробляється частина масиву не зменшиться до одного елемента.
Очевидно, в кінець масиву кожен раз потрапляє максимальний елемент з поточної піраміди, тому в правій частині поступово виникає впорядкована послідовність.
Код зовнішньої процедури сортування:
Яке швидкодію отриманого алгоритму?
Побудова піраміди займає O (n log n) операцій, причому більш точна оцінка дає навіть O (n) за рахунок того, що реальний час виконання downheap залежить від висоти вже створеної частини піраміди.
Друга фаза займає O (n log n) часу: O (n) раз береться максимум і відбувається просіювання колишнього останнього елемента. Плюсом є стабільність методу: середнє число пересилань (n log n) / 2, і відхилення від цього значення порівняно малі.
Пірамідальна сортування не використовує додаткової пам'яті.
Метод не є стійким: по ходу роботи масив так "перетрушується", що вихідний порядок елементів може змінитися випадковим чином.
Поведінка неприродно: часткова впорядкованість масиву ніяк не враховується.