Поєднувана купа

В інформатиці, поєднувана купа — абстрактний тип даних, який є купою, що підтримує операцію злиття.

Визначення

Поєднувана купа підтримає такі звичайні для куп операції:

• Make-Heap(), створити нову купу.
• Insert(H,x), вставити елемент x у купу H.
• Min(H), повернути мінімальний елемент.
• Extract-Min(H), видалити мінімальний елемент з купи і повернути його.

А також одну додаткову, яка її вирізняє:

• Merge(H1,H2), створити і повернути нову купу, яка містить елементи з H1 і H2, ця операція знищує початкові купи.

Тривіальне втілення

Реалізувати поєднувану купу із використанням простої купи нескладно:

1. Merge(H1,H2):
2.     x ← Extract-Min(H2)
3.     while x ≠ Nil
4.         Insert(H1, x)
5.         x ← Extract-Min(H2)

Однак така реалізація буде марнотратною, оскільки кожна операція Extract-Min(H) і Insert(H,x) зазвичай мають слідкувати за дотриманням властивості купи.

Ефективніші реалізації

Приклади поєднуваних куп:

• Купа Фібоначчі
• Біноміальна купа
• Купа двійкування

Див. також

• Адресовна купа