В інформатиці, поєднувана купа — абстрактний тип даних, який є купою, що підтримує операцію злиття.
Визначення
Поєднувана купа підтримає такі звичайні для куп операції:
Make-Heap(), створити нову купу. Insert(H,x), вставити елемент x у купу H. Min(H), повернути мінімальний елемент. Extract-Min(H), видалити мінімальний елемент з купи і повернути його. А також одну додаткову, яка її вирізняє: Merge(H1,H2), створити і повернути нову купу, яка містить елементи з H1 і H2, ця операція знищує початкові купи.
Тривіальне втілення
Реалізувати поєднувану купу із використанням простої купи нескладно:
Merge(H1,H2): x ← Extract-Min(H2) while x ≠ Nil Insert(H1, x) x ← Extract-Min(H2)
Однак така реалізація буде марнотратною, оскільки кожна операція Extract-Min(H) і Insert(H,x) зазвичай мають слідкувати за дотриманням властивості купи.
Ефективніші реалізації
Приклади поєднуваних куп:
Купа Фібоначчі Біноміальна купа
Див. також Адресовна купа
Примітки