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\).
C++
1
2
3
4
5
6
7
8
9
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.

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用