Покажем, что основные операции с кучей Фибоначчи могут быть реализованы в виде последовательности двух процедур: link(i, j) и cut(i).

• link(i, j)
  Процедура link(i, j) применяется к двум различным корневым узлам i и j равного ранга.
  Если key(j) <= key(i), то вводим дугу (i, j) (в куче Фибоначчи узел j становится отцом узла i).

Если key[j] > key[i], товводим дугу (j, i) (узел i становится отцом узла j)
• cut(i)
  Удаляем дугу (i, pred[i]) (в куче узел i становится корневым узлом).

Для кучи Фибоначчи определим основные операции и покажем, что для реализации каждой из них достаточно использования последовательности процедур link и cut.

• find_min(i, H) – операция нахождения ключа узла
• minkey, где minkey – узел с минимальным ключом.
• insert(x, H) – операция добавляет к куче корневое дерево, состоящее из единственного узла с ключом x. После этого может быть нарушен инвариант 3. Для его восстановления может потребоваться последовательность процедур link.
• delete_min(x, H) – операция удаления минимального элемента из кучи Фибоначчи. Находим корневое дерево с корнем minkey. Отрезаем с помощью процедуры cut всех сыновей узла minkey и записываем их в список list. Упорядочим элементы списка list в порядке неубывания рангов (например, с помощью черпачной сортировки). Для обеспечения инварианта 3 поступаем следующим образом. Извлекаем из списка list множество r₁, ..., r_t корней ранга k. Если t > 1, выполняем процедуру link(r_i, r_i+1), i = 1, 3, 5, ..., t-1 и записываем полученные корни ранга k + 1 в черпак k-1, k = 0, 1, ..., 2 logn + 1. Получим список list, в котором нет узлов одинакового ранга. Сканируем все корневые узлы (которые хранятся в списке list и в массиве bucket(k), k = 0, 1, ..., 2 logn + 1), и с помощью процедуры link востанавливаем инвариант 3. Следует заметить, что нет необходимости в поддержке инварианта 2, поскольку он выполнен.

Восстановление инварианта 2

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

lost(i):

• для корневого узла lost(i) = 0;
• для некорневого узла lost(i) равен числу сыновей, которые узел i потерял, после того, как стал некорневым узлом.

Начальная процедура cut может породить другие процедуры cut, которые назовем порожденными процедурами cut. Узлы к которым применяется операция cut будем хранить в списке list.

Восстановление инварианта 2 осуществляется следующим образом: если значение lost(i) = 2, то к узлу i применим процедуру cut(i). В свою очередь процедура cut(i) может породить процедуру cut(pred(i)) для узла k = pred(i), если lost(k) = 2 и т.д. до тех пор, пока не будет выполнен инвариант 2. Узлы, к которым применены начальная процедура cut, и последовательность порожденных процедур cut, а также их ранги сохраняем в списке list.

Восстановление инварианта 3

Инвариант 3 требует, чтобы никаких два корневых узла не имели одинакового ранга. Для поддержки инварианта 3 вводим индекс bucket(k):

• для каждого некорневого узла i кучи Фибоначчи ранга k полагаем bucket(k) = 0 и
• bucket(k) = i, если некоторый корневой узел i имеет ранг, равный k;

Начальная процедура link может породить последовательность других процедур link, которые назовем порожденными процедурами link.

Предположим, что, работая с кучей Фибоначчи, мы создали корень j ранга k и куча содержит другой корневой узел i этого же ранга k. Тогда мы повторяем следующую процедуру для поддержки инварианта 3: выполняется процедура link(i, j), которая объединяет два корневых дерева с корневыми узлами ранга k в новое корневое дерево с корнем ранга k + 1. Пусть l – корень нового дерева. Если bucket(k + 1) = t <> 0, то среди набора корневых деревьев имеется корневое дерево с корнем t ранга k + 1. Выполняем снова процедуру link(l, t) объеденения двух корневых деревьев с корнями ранга k + 1 в одно корневое дерево с корнем ранга k + 2 и снова проверяем значение bucket(k + 2) и т.д. Этот процесс выполнения процедур link продолжается до тех пор, пока не будет сохранен инвариант 3. После выполнения каждой процедуры link(i, j) необходимо корректировать элементы структуры данных.