Фибоначчиева куча
Материал из Википедии — свободной encyclopedia
У этого термина существуют и другие значения, см. Куча.
Фибоначчиева куча (англ. Fibonacci heap) — структура данных, представляющая собой набор деревьев, упорядоченных в соответствии со свойством неубывающей пирамиды. Фибоначчиевы кучи были введены Майклом Фредманом и Робертом Тарьяном в 1984 году.
Структура является реализацией абстрактного типа данных «Очередь с приоритетом», и замечательна тем, что операции, в которых не требуется удаление, имеют амортизированное время работы, равное (для двоичной кучи и биномиальной кучи амортизационное время работы равно ).
Кроме стандартных операций INSERT
, MIN
, DECREASE-KEY
, фибоначчиева куча позволяет за время выполнять операцию UNION
слияния двух куч.