Повний бінарне дерево
бінарне дерево
Серед дерев виділяють особливий підклас, званий бінарними деревами. Бінарне дерево - кореневе дерево, кожна вершина якого має не більше двох дочірніх, найчастіше чітко впорядкованих: ліву і праву. Наприклад, це дерево є бінарним:
Серед бінарних дерев окремо виділяють повні бінарні дерева. всі вершини яких мають по дві дочірніх, крім листя, які розташовані на однаковій глибині:
Також повними часто називають бінарні дерева, у яких повністю заповнені всі рівні, крім останнього:
При 1-індексації вершин за рівнями, наведеної вище, існують прості формули переходу між вершинами. Для вершини з індексом $ v $ формули для спуску вліво, спуску вправо, і підйому вгору виглядають наступним чином:
$$ l = 2v \\ r = 2v + 1 \\ p = \ left \ lfloor \ right \ rfloor $$
У зв'язку з цим повні бінарні дерева найчастіше зберігають не у вигляді списку суміжності, а у вигляді простого масиву, де $ tree [v] $ - деяке значення, присвоєне вершині з індексом $ v $. Для обходу дерева використовуються формули, наведені вище.
Варто відзначити, що висота (кількість рівнів) повного бінарного дерева з $ N $ вершин дорівнює $ \ log N $. Це властивість часто використовується для оцінки складності різних алгоритмів.
Купа (англ. Heap) - одна з найпростіших структур даних, заснованих на деревах. Купа використовується для підтримування певної кількості елементів з можливістю швидкого знаходження максимуму (або мінімуму, це не принципово).
Класична купа підтримує наступні операції:
- Додати елемент (Складність: $ O (\ log N) $)
- Знайти максимум (Складність: $ O (1) $)
- Витягти максимальний елемент (Складність: $ O (\ log N) $)
Елементи в купі зберігаються у вигляді повного бінарного дерева. Головне його властивість (інваріант купи) формулюється так:
Елемент в кожній вершині більше або дорівнює елементів у всіх дочірніх вершинах.
З цієї властивості випливає, що мінімальний елемент завжди буде знаходитися в корені дерева.
При додаванні в купу нового елемента, йому присвоюється перший доступний індекс. Тобто, бінарне дерево заповнюється за рівнями зліва направо. Після додавання елемента можливо, що інваріант купи перестане виконуватися, так як новий елемент буде більше свого прямого предка. У таких випадках просто міняємо елемент місцями з прямим предком. Якщо інваріант купи все ще не виконується, міняємо його місцями з новим предком, і так далі, поки купа ненормалізується. Така операція називається проштовхуванням вгору.
Під час вилучення максимального елемента скористаємося такою хитрістю: перемістимо останній елемент в купі (крайній правий на останньому рівні) в корінь дерева на місце видаленого максимуму. Це майже напевно порушить інваріант, так як новий "максимум" буде менше елементів в дочірніх вершинах. Порівняємо два дочірніх елемента, виберемо з них більший, і поміняємо його місцями з поточним "максимумом". Повторюємо цю операцію, поки інваріант не відновиться. Це називається проштовхуванням вниз.
Реалізація
Поняття черги з пріоритетом
Ви можете почути, як замість терміна "купа" використовується термін "чергу з пріоритетом". На практиці вони синоніми, хоча різниця в значенні все-таки присутня.
Черга з пріоритетом - абстракная структура даних, що дозволяє підтримувати безліч елементів, знаходити і витягати мінімум з нього, тоді як купа - конкретна структура даних, заснована на повному бінарному дереві. Будь-яка купа є чергою з пріоритетом, але не будь-яка чергу з пріоритетом (в теорії) є купою (на практиці майже що будь-яка). Ви можете реалізувати підтримку безлічі з витяганням максимуму за допомогою простого масиву, вона буде мати складність операцій $ O (N) $, але все одно бути чергою з пріоритетом.
(Якщо ви знайомі з об'єктно-орієнтованим програмуванням, то чергу з пріоритетом - інтерфейс, а купа - клас, який реалізує його.)
Черга з пріоритетом в стандартній бібліотеці C ++
У стандартній бібліотеці C ++ присутній реалізація купи, що підтримує всі операції, наведені вище. Це клас std :: priority_queue
За замовчуванням використовується купа для пошуку максимуму. Для використання купи для пошуку мінімуму потрібно використовувати тип std :: priority_queue