19-1 Alternative implementation of deletion

Professor Pisano has proposed the following variant of the $\text{FIB-HEAP-DELETE}$ procedure, claiming that it runs faster when the node being deleted is not the node pointed to by $H.min$.

cpp PISANO-DELETE(H, x) if x == H.min FIB-HEAP-EXTRACT-MIN(H) else y = x.p if y != NIL CUT(H, x, y) CASCADING-CUT(H, y) add x's child list to the root list of H remove x from the root list of H

a. The professor's claim that this procedure runs faster is based partly on the assumption that line 7 can be performed in $O(1)$ actual time. What is wrong with this assumption?

b. Give a good upper bound on the actual time of $\text{PISANO-DELETE}$ when $x$ is not $H.min$. Your bound should be in terms of $x.degree$ and the number $c$ of calls to the $\text{CASCADING-CUT}$ procedure.

c. Suppose that we call $\text{PISANO-DELETE}(H, x)$, and let $H'$ be the Fibonacci heap that results. Assuming that node $x$ is not a root, bound the potential of $H'$ in terms of $x.degree$, $c$, $t(H)$, and $m(H)$.

d. Conclude that the amortized time for $\text{PISANO-DELETE}$ is asymptotically no better than for $\text{FIB-HEAP-DELETE}$, evenwhen $x \ne H.min$.

a. It can take actual time proportional to the number of children that $x$ had because for each child, when placing it in the root list, their parent pointer needs to be updated to be $\text{NIL}$ instead of $x$.

b. Line 7 takes actual time bounded by $x.degree$ since updating each of the children of $x$ only takes constant time. So, if $c$ is the number of cascading cuts that are done, the actual cost is $O(c + x.degree)$.

c. We examine the number of trees in the root list $t(H)$ and the number of marked nodes $m(H)$ of the resulting Fibonacci heap $H'$ to upper-bound its potential. The number of trees $t(H)$ increases by the number of children $x$ had ($=x.degree$), due to line 7 of $\text{PISANO-DELETE}(H, x)$. The number of marked nodes in $H'$ is calculated as follows. The first $c - 1$ recursive calls out of the $c$ calls to $\text{CASCADING-CUT}$ unmarks a marked node (line 4 of $\text{CUT}$ invoked by line 5 of $\text{CASCADING-CUT}$). The final $c$th call to $\text{CASCADING-CUT}$ marks an unmarked node (line 4 of $\text{CASCADING-CUT}$), and therefore, the total change in marked nodes is $-(c - 1) + 1 = -c + 2$. Therefore, the potential of H' is

$$\Phi(H') \le t(H) + x.degree + 2(m(H) - c + 2).$$

d. The asymptotic time is

$$\Theta(x.degree) = \Theta(\lg(n)),$$

which is the same asyptotic time that was required for the original deletion method.