Изменения

Вставка элемента в фибоначчиеву кучу также тривиальна: создается новая куча из одного элемента и сливается с текущей. Амортизированная стоимость Для оценки амортизированной стоимости операции: рассмотрим исходную кучу <tex> H </tex> и получившуюся в результате вставки нового элемента кучу <tex> H' </tex>. <tex> t[H'] = t[H] + 1 </tex> и <tex> m[H'] = m[H] </tex>. Следовательно, увеличение потенциала составляет <tex> (создание кучиt[H] + 1 + 2m[H]) + 2 - (слияние куч t[H] + релаксация минимума2m[H]) + = 1 </tex>. Так как реальное время работы составляет <tex> O(изменение потенциала1) = 4 = </tex>, то амортизированная стоимость данной операции также равна <tex> O(1) </tex>.