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

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

Визначення

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

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) зазвичай мають слідкувати за дотриманням властивості купи.

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

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

Див. також

Примітки

Т. Кормен; Ч. Лейзерсон; Р. Рівест; К. Стайн (2009) [1990]. 19 Фібоначчієві купи. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN .

[IA-1] Т. Кормен; Ч. Лейзерсон; Р. Рівест; К. Стайн (2009) [1990]. 19 Фібоначчієві купи. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN .