Page 57 - 6110

Лекція № 12

КУПА

Купа або піраміда (heap) в інформатиці – це спеціалізована
деревовидна структура даних, в якій існують певні властивості
впорядкованості. Така структура даних повинна задовільняти
основній властивості купи: нехай А та B є елементами купи,
такими, що B підпорядковане A (B – це дитина А). Тоді значення B
не повинно перевищувати А, тобто val[B] ≤ val[A].
Найбільш уживаним класом куп є бінарні купи.
Базові операції з купою такі:
- підтримка основної властивості купи;
- побудова купи з невпорядкованого масиву;
- сортування купи;
- видалення найменшого елемента;
- отримання найбільшого елемента;
- додавання елемента.
Купи часто використовуються для моделювання черг з
пріоритетами.
Бінарна купа (binary heap) – це структура даних, що є
масивом, який можна розглядати як майже повне бінарне дерево.
Кожен вузол цього дерева відповідає певному елементу масиву. На
всіх рівнях, крім, можливо останнього, дерево повністю заповнене
(заповнений рівень – це такий, що містить максимально можливу
кількість вузлів). Останній рівень заповнюється послідовно зліва
направо до тих пір, доки в масиві не закінчаться елементи.
Для масиву A у корені дерева знаходиться елемент A[1]. Далі
дерево будується за наступним принципом: якщо якомусь вузлу
відповідає індекс i, то індекс його батьківського вузла
обчислюється за допомогою процедури Parent(i), індекс лівого
дочірнього вузла знаходиться за допомогою процедури Left(i), а
індекс правого дочірнього вузла визначається за допомогою
процедури Right(i):
Parent(i)
return [i/2]

Left(i)
return 2i

Right(i)
return 2i + 1

56