Фібоначчієва купа

Матеріал з Вікіпедії — вільної енциклопедії.
(Перенаправлено з Купа Фібоначчі)
Перейти до: навігація, пошук
Операція Амортизаційний час
Make-Heap \Theta(1)
Insert \Theta(1)
Minimum \Theta(1)
Extract-Min O(\lg n)
Union \Theta(1)
Decrease-Key \Theta(1)
Delete O(\lg n)

Купа Фібоначчі — абстрактна структура даних, що являє собою ефективне втілення черги з пріоритетом.

З теоретичної точки зору купи Фібоначчі особливо бажані, коли кількість Extract-Min і Delete операцій мала відносно кількості інших операцій. Це відбувається у багатьох застосуваннях. Наприклад, деякі алгоритми на графах можуть викликати Decrease-Key на кожному ребрі. Для насиченого графу амортизаційний час \Theta(1) кожного виклику Decrease-Key складається у велику перевагу в порівнянні з \Theta(\lg n) у найгіршому випадку в бінарній купі. Це можна побачити на прикладі алгоритмів про найкоротші шляхи з одного входу і мінімального кістякового дерева. З практичної точки зору сталий множник прихований у складності алгоритму і складність у програмуванні купи Фібоначчі роблять її менш бажаною ніж звичайну бінарну або d-арну купу для більшості застосувань.

Структура купи[ред.ред. код]

Купа Фібоначчі являє собою набір дерев кожне з яких є мінкупою.

Кожен вузол x містить вказівник x.p на свого предка і вказівник x.child на один з його нащадків. Нащадки зв'язані в циклічний двобічно зв'язаний список. Кожен нащадок y має вказівники y.left та y.right. Якщо вузол є єдиним нащадком, тоді y = y.left = y.right. Нащадки елемента можуть перебувати у будь-якому порядку. Використання двобічно зв'язаних списків уможливлює вставляння і видалення елементів за час O(1), а також зв'язування двох списків за O(1). Також кожен вузол має атрибути x.degree, що дорівнює кількості нащадків, і атрибут x.mark, що показує чи втратив вузол нащадка з моменту як він став нащадком свого поточного предка.

Доступ до купи відбувається через вказівник H.min, який вказує на корінь дерева з найменшим ключем. Якщо дерево порожнє, то H.min дорівнює NIL.

Для оцінки швидкодії ми використовують метод потенціалів із потенціальною функцією \Phi(H) = t(H) + 2m(H). Де t(H) дає кількість дерев у купі, а m(H) — кількість позначених вузів.

Джерела[ред.ред. код]