W ten sposób korzeniem pozostaje najmniejszy wierzchołek. Aby efektywnie wyszukiwać drzewa o tym samym stopniu tworzymy tablicę wskaźników o długości O(log n) gdzie trzymamy wskaźniki do drzew o kolejnych rzędach. Jeśli rozpatrujemy drzewo o rzędzie k, ale w k-tej komórce tablicy istnieje już wskaźnik, oznacza to ze powinniśmy złączyć oba drzewa i zapisać w komórce k+1. Aktualny koszt wynosi O(n +m), gdzie m jest liczbą korzeni na początku drugiej fazy algorytmu. Finalnie otrzymujemy nie więcej niż O(log n) korzeni o różnych stopniach.
Podczas trzeciego etapu przeglądamy korzenie drzew w celu znalezienia minimum, co zajmuje O(log n). Łączny zamortyzowany koszt wynosi więc O(log n). mały|250x250px|Kopiec Fibonacciego po zmniejszeniu klucza 9 do 0 Operacje zmniejszenia klucza zaczyna od zmniejszenia wartości zadanego wierzchołka i w razie gdy nowa wartość zaburza porządek kopcowy (czyli wierzchołek jest mniejszy niż rodzic) wywołujemy operacje odcinania rozważanego wierzchołka.
Operacja odcinania wierzchołka x odcina go od jego ojca (y) i dołącza do listy korzeni kopca.