Рассмотрим семейство корневых деревьев и для него определим две процедуры link(i, j) и cut(i). Процедура link(i, j) состоит в слиянии двух деревьев одинакового ранга, корнями которых являются узлы i и j. Процедура cut(i) состоит в том, что образуется новое дерево, корнем которого является узел i, а i перестает быть сыном узла j = pred[i].

Для любого узла необходимо иметь информацию о предках, потомках и ранге узлов соответствующего дерева (под рангом узла понимается количество его сыновей):

• pred[i] – отец узла i в наборе корневых деревьев. Узел i , не имеющий отца является корневым узло. В этом случае pred[i] = 0.
• succ[i] – множество сыновей узла i. Это множество можно хранить в виде двунаправленного списка.
• rank[i] – число сыновей узла i (rank[i] = [ succ[i] ])
• minkey – узел с минимальным значением ключа в наборе корневых деревьев.

Процедуры link(i, j) и cut(i) требуют O(1) времени для выполнения.

Существует зависимость между числом процедур link(i, j) и cut(i) при работе со структурой данных куча Фибоначчи. Рассмотрим функцию потенциалов (potential function), определяемую как количество корневых деревьев. Каждая процедура link(i, j) уменьшает число корневых деревьев на 1 и каждая процедура cut(i) увеличивает их число на 1. Общее число уменьшений числа корневых деревьев в куче Фибоначчи ограничено начальным числом корневых деревьев (m) плюс общее число их уменьшений. Следующее свойство очевидно.

Число процедур link(i, j) равно как максимум m плюс число процедур cut(i).

Обозначим через G(k) минимальное число узлов, содержащихся в поддереве с корнем в узле ранга k в куче Фибоначчи, тогда G(k) >= F(k)

Максимально возможный ранг любого узла в куче Фибоначчи равен 2 log n + 1, следовательно куча Фибоначчи состоит из не более чем из 2 log n + 1 корневых деревьев.