19.3 Decreasing a key and deleting a node

19.3-1

Suppose that a root $x$ in a Fibonacci heap is marked. Explain how $x$ came to be a marked root. Argue that it doesn't matter to the analysis that $x$ is marked, even though it is not a root that was first linked to another node and then lost one child.

$x$ came to be a marked root because at some point it had been a marked child of $H.min$ which had been removed in $\text{FIB-HEAP-EXTRACT-MIN}$ operation. See figure 19.4 for an example, where the node with key $18$ became a marked root. It doesn't add the potential for having to do any more actual work for it to be marked. This is because the only time that markedness is checked is in line 3 of cascading cut. This however is only ever run on nodes whose parent is non $\text{NIL}$. Since every root has $\text{NIL}$ as it parent, line 3 of cascading cut will never be run on this marked root. It will still cause the potential function to be larger than needed, but that extra computation that was paid in to get the potential function higher will never be used up later.

19.3-2

Justify the $O(1)$ amortized time of $\text{FIB-HEAP-DECREASE-KEY}$ as an average cost per operation by using aggregate analysis.

Recall that the actual cost of $\text{FIB-HEAP-DECREASE-KEY}$ is $O(c)$, where $c$ is the number of calls made to $\text{CASCADING-CUT}$. If $c_i$ is the number of calls made on the $i$th key decrease, then the total time of $n$ calls to $\text{FIB-HEAPDECREASE-KEY}$ is $\sum_{i = 1}^n O(c_i)$.

Next observe that every call to $\text{CASCADING-CUT}$ moves a node to the root, and every call to a root node takes $O(1)$. Since no roots ever become children during the course of these calls, we must have that $\sum_{i = 1}^n c_i = O(n)$. Therefore the aggregate cost is $O(n)$, so the average, or amortized, cost is $O(1)$.