Поєднувана купа
Перейти до навігації
Перейти до пошуку
В інформатиці, поєднувана купа — абстрактний тип даних, який є купою, що підтримує операцію злиття.
Визначення[ред. | ред. код]
Поєднувана купа підтримає такі звичайні для куп операції:[1]
Make-Heap(), створити нову купу.Insert(H,x), вставити елементxу купуH.Min(H), повернути мінімальний елемент.Extract-Min(H), видалити мінімальний елемент з купи і повернути його.
А також одну додаткову, яка її вирізняє:[1]
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 Fibonacci Heaps. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. с. 505. ISBN 0-262-03384-4.