Структури даних: 2-3 купа (2-3 heap)

Питання ефективного способу реалізації черзі з пріоритетом деякою структурою даних залишається актуальним протягом довгого часу. Відповідь на це питання завжди є певним компромісом між об'ємом пам'яті, необхідним для зберігання даних і часом роботою операцій над чергою.

У комп'ютерних науках для ефективної реалізації черзі з пріоритетом використовуються структури у вигляді купи.

Купа — це спеціалізована структура даних типу дерево, що задовольняє властивості купи: якщо B є вузлом-нащадком вузла A, то ключ(A) ≥ ключ(B). З цього випливає, що елемент з найбільшим ключем завжди є кореневим вузлом купи, тому іноді такі купи називають max-купами (в якості альтернативи, якщо порівняння перевернути, то найменший елемент буде завжди кореневим вузлом, такі купи називають min-купами). Не існує ніяких обмежень щодо того, скільки вузлів-нащадків має кожен вузол купи, хоча на практиці їх кількість зазвичай не більше двох. Купи мають вирішальне значення в деяких ефективних алгоритмів на графах, таких як алгоритм Дейкстри і сортування методом піраміди.

Одними з найбільш вивчених і добре зарекомендували себе структур даних для зберігання і роботою з чергою з пріоритетом є Бінарна Купа (Binary Heap) і Купа Фібоначчі (Fibonacci Heap). Але дані структури мають деякими особливостями.

Наприклад, бінарна купа для основних операцій має трудомісткість Θ(logn), крім знаходження мінімального, а для злиття таких куп потрібно лінійний час (!). Зате для зберігання такої купи необхідно мало пам'яті в порівнянні з іншими купами.

Купа Фібоначчі має балансуванням при витяганні вузла з купи, що дозволяє скоротити трудомісткість основних операцій. При великій кількості послідовних операцій додавання Фибоначчиева купа росте в ширину і балансування відбувається лише при операції видалення мінімуму, тому операція отримання мінімуму може вимагати значних витрат часу!

Рішенням над цією проблемою зайнявся Тадао Такаока (Tadao Takaoka), опублікувавши свою роботу «2-3 heap» в 1999 році…

Трохи про структуру «2-3 Heap»
2-3 купа (2-3 heap) — це структура даних типу дерево, що задовольняє властивості купи (min-heap, max-heap). Є альтернативою купи Фібоначчі (Fibonacci heap). Складається з 2-3 дерев.

Рішення, яке пропонує 2-3 heap, полягає в тому, що на відміну від Купи Фібоначчі, 2-3 купа виконує балансування не тільки стирання, але і при додаванні нових елементів, знижуючи обчислювальне навантаження при витяганні мінімального вузла з купи.

Кількість дітей вершини t довільного дерева T назвемо ступенем (degree) цієї вершини, а ступенем дерева назвемо ступінь його кореня.

2-3 деревами називаються дерева T0, T1, T2, ..., визначені індуктивно. Дерево T0 складається з єдиної вершини. Під деревом Tі розуміється дерево, складене із двох дерев Ti-1 небудь з трьох: при цьому корінь кожного наступного стає самим правим дитиною кореня попереднього.

Деревами 2-3 купи назвемо дерева H[i]. Дерево H[i] — це або порожнє 2-3 дерево, або одне, або два 2-3 дерева ступеня i, сполучені аналогічно деревах Tі.

2-3 купа — це масив дерев H[i] (i=0..n), для кожного з яких виконується властивість купи.


рис. Візуальне подання купи

Структура вузла

Кожен вузол має вказівники на інші вузли (поля мають стрілки), службові поля та пара ключ (пріоритет) — значення.


Основні операції

Пошук мінімального 2-3 heap (FindMin)

Мінімальний елемент купи знаходиться в корені одного з дерев купи. Щоб знайти мінімальний вузол, потрібно пройтися по деревах.

Підтримуючи покажчик на мінімальний вузол в купі ми можемо знаходити цей вузол за константна час ( Θ(1) )

Вставка в 2-3 heap (Insert)

  1. Для додавання нового елемента створимо дерево H[0] містить одну вершину
  2. Проведемо операцію додавання цього дерева в купу. При додаванні дерева ступеня i в купу можливі наступні варіанти:
    1. Якщо дерева з таким пріоритетом немає, то просто додаємо його в купу.
    2. Інакше отримуємо таке дерево з купи і з'єднуємо з доданих, після додаємо отримане дерево в купу
  3. Після додавання поправляємо покажчик на мінімальний корінь



рис. Анімація послідовного додавання елементів в 2-3 купу

Видалення мінімального елемента з купи

Мінімальний елемент купи знаходиться в корені одного з дерев купи, припустимо в H[i] — знайдемо його за допомогою FindMin. Винесемо дерево H[i] з купи і видалимо його корінь, при цьому дерево розпадеться на піддерева, які ми згодом додамо в купу.

Будемо видаляти корінь рекурсивно: якщо дерево складається з однієї вершини, то просто видалимо її; інакше від'єднуємо від кореня самого правого дитини і продовжимо видалення.


Зменшення ключа у елементі

Першим ділом ми можемо вільно зменшити ключ у необхідного сайту. Після цього необхідно перевірити: якщо вузол знаходиться в корені дерева, то більше нічого робити не потрібно, інакше потрібно буде витягнути цей вузол з усіма поддеревьями і вставити його назад в купу (з уже зміненим ключем).


Об'єднання двох куп в одну

Є дві купи, які потрібно об'єднати в одну. Для цього ми будемо по черзі витягуємо всі 2-3 дерева з другої купи і вставляти їх в першу купу. Після цього потрібно буде поправити лічильник кількості вузлів: підсумовуємо кількість елементів в першій і в другій купі і записуємо результат в лічильник в першій купі, а в другій купі встановлюємо лічильник 0.

Порівняння трудоемкостей операцій з іншими алгоритмами
У таблиці наведено трудомісткості операцій черзі з пріоритетом (в гіршому випадку, worst case)
Символом '*' відзначена амортизована складність операцій
Операція Binary Heap Біном Heap Fibonacci Heap 2-3 Heap
FindMin Θ(1) O(logn) Θ(1)* Θ(1)*
DeleteMin Θ(logn) Θ(logn) O(logn)* O(logn)*
Insert Θ(logn) O(logn) Θ(1)* Θ(1)*
DecreaseKey Θ(logn) Θ(logn) Θ(1)* Θ(1)*
Merge/Union Θ(n) Ω(logn) Θ(1) Θ(1)*


Дякуємо за приділену увагу!

Вихідний код реалізації на C++, що ґрунтується на статті автора 2-3 Heap доступний на GitHub під MIT.

PS: При написанні курсового проекту по цій темі, я зрозумів, що інформації в Рунеті практично немає, тому вирішив внести свої пару копійок в цю справу, розповівши зацікавленій спільноті про це алгоритмі.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.