Editing Fibonacci heap (section)

=== Decrease-key ===
[[Image:Fibonacci heap-decreasekey.png|246x246px|thumb|Figure 4. Fibonacci heap from Figure 1 after decreasing key of node 9 to 0.]]If decreasing the key of a node <math>x</math> causes it to become smaller than its parent, then it is cut from its parent, becoming a new unmarked root. If it is also less than the minimum key, then the minimum pointer is updated.

We then initiate a series of ''cascading cuts'', starting with the parent of <math>x</math>. As long as the current node is marked, it is cut from its parent and made an unmarked root. Its original parent is then considered. This process stops when we reach an unmarked node <math>y</math>. If <math>y</math> is not a root, it is marked. In this process we introduce some number, say <math>k</math>, of new trees. Except possibly <math>x</math>, each of these new trees loses its original mark. The terminating node <math>y</math> may become marked. Therefore, the change in the number of marked nodes is between of <math>-k</math> and <math>-k+2</math>. The resulting change in potential is <math>k+2(-k+2)=-k+4</math>. The actual time required to perform the cutting was <math>O(k)</math>. Hence, the amortized time is <math>O(k) + c(-k+4)</math>, which is constant, provided <math>c</math> is sufficiently large.