Піраміда (сортувальне дерево, бінарна купа) −
бінарне дерево з впорядкованим листям (корінь дерева − найменший чи найбільший
елемент). Піраміду можна уявити у вигляді масиву. Перший елемент піраміди є найменшим
або найбільшим, що залежить від ключа сортування. Його називають коренем або вершиною піраміди.
Основна
властивість бінарного дерева: значення
лівого нащадка менше значення батька, а значення правого нащадка більше
значення батька для кожного вузла дерева. Батьком з двох синів стає найбільше число. Процес
повторюється, доки не буде виділене одне число, найбільше, яке стане корнем
утвореного дерева. У разі відсутності одного числа, батьком стає єдиний нащадок
(син). Число, що попало в корінь замінюється на безмежність. Процес
повторюється для знаходження наступного найбільшого числа. Задана послідовність буде впорядкована у низхідному порядку за (n-1) кроків.
Просіювання − це побудова нової піраміди за наступним алгоритмом: новий
елемент поміщається у вершину дерева, далі він переміщається ("просівається")
по шляху вниз на основі порівняння з дочірніми елементами. Спуск завершується,
якщо результат порівняння з дочірніми елементами відповідає ключу сортування.
Принцип
побудови дерева має наступний вигляд: якщо надходить черговий елемент масиву,
то починаючи з кореня дерева (в залежності від порівняння поточного елемента з
черговою вершиною) йдемо вліво або вправо від неї до тих пір, поки не знайдемо
відповідну вершину, до якої можна підключити нову вершину з поточним ключем.
Залежно від результату порівняння ключів, нову вершину робимо лівої чи правої
для знайденої вершини.
Комментариев нет:
Отправить комментарий