Купа Фібоначчі

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Ку́па Фібона́ччі (англ. Fibonacci heap) — структура даних, що являє собою набір дерев, впорядкованих згідно із властивістю неспадної піраміди. Купи Фібоначчі були розроблені Майклом Фредманом та Робертом Тар'яном у 1984 році та опубліковані в науковому журналі в 1987 році.

Структура є реалізацією абстрактного типу даних «Черга з пріоритетом». Операції вставки, знаходження мінімального елемента та злиття (об'єднання) мають амортизований час роботи О(1) (це краще, ніж у бінарної та біноміальної куп, для яких амортизований час дорівнює О(log(n))). Операції видалення виконуються за О(log(n)).

Посилання[ред.ред. код]