Пирамиды

 

Пирамиды поддерживают следующие пять операций.

 

Маке_Неар() создает и возвращает новую пустую пирамиду.

Insert(H, х) вставляет узел х (с заполненным полем key) в пирамиду H.

Minimum(H) возвращает указатель на узел в пирамиде H, обладающий минимальным ключом.

Extract_Min(H) удаляет из пирамиды H узел, ключ которого минимален, возвращая при этом указатель на этот узел.

Union(H1, H2) создает (и возвращает) новую пирамиду, которая содержит все узлы пирамид Н1 и Н2. Исходные пирамиды при выполнении этой операции уничтожаются. Кроме того, структуры данных, описанные в этих главах, поддерживают следующие две операции.

Decrease_Key( H, x, к) присваивает узлу х в пирамиде H новое значение ключа к (предполагается, что новое значение ключа не превосходит текущего.

Delete(H, х) удаляет узел х из пирамиды H.

 

 

Биномиальные пирамиды, поддерживают все перечисленные операции со временем выполнения О (lg n) в худшем случае (n — общее количество элементов в пирамиде (или в двух пирамидах в случае операции Union). При необходимости поддержки операции Union биномиальные пирамиды превосходят бинарные пирамиды, поскольку последним в наихудшем случае требуется для объединения двух пирамид время в Θ(n).

Фибоначчиевы пирамиды представляют собой усовершенствованные биномиальные пирамиды — по крайней мере, теоретически. Для оценки производительности Фибоначчиевых пирамид используется амортизированное время выполнения операций. Операции Insert, Minimum и Union у Фибоначчиевых пирамид имеют амортизированное (а также фактическое) время работы, равное O(1), а операции Extract_Min и Delete — О(logn). Главное преимущество Фибоначчиевых пирамид, однако, заключается в том, что операция Decrease_Key имеет амортизированное время O(1). Именно это свойство делает Фибоначчиевы пирамиды ключевым компонентом ряда наиболее быстрых асимптотических алгоритмов для работы с графами.

 

Биномиальная пирамида представляет собой коллекцию биномиальных деревьев. Рекурсивное определение биномиального дерева, примеры биномиальных деревьев и альтернативное представление биномиальных деревьев представлены на рис.

Биномиальная пирамида (binomial heap) H представляет собой множество биномиальных деревьев.