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

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

Визначення

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

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

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

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

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

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

Див. також
  • Адресовна купа

Примітки
  1. Томас Кормен; Чарльз Лейзерсон, Рональд Рівест, Кліфорд Стайн (2009) [1990]. 19 Fibonacci Heaps. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. с. 505. ISBN 0-262-03384-4.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.