Consider the DECREASE-KEY operation in a Fibonacci heap. Let us generalize the cascading-cut rule to cut...

 

Transcribed Image Text:

Consider the DECREASE-KEY operation in a Fibonacci heap. Let us generalize the cascading-cut rule to cut a node x from its parent as soon as it loses its third child (this extends the method in the lecture which cut x from its parent if it loses its second child). Let us call this a 3F heap. Assume the following fact for the 3F heap (you can prove this on your own, you do not need to submit your proof). 7 Fact. Let a be a node in a 3F heap, and let its degree be d. Let y₁, yd be the children of r in the order in which they were linked to x, from the earliest to the latest. Establish that the degree of yi is at least i - 3 for i ≥ 3. (i) (6 pts) Let x be a node of degree d in a 3F heap and let size(r) be the number of nodes in the subtree rooted at r. Establish that size(x) ≥ V(d), where V(i) satisfies the following: V(i) =i+1 for 0 ≤ i ≤ 2, and V(i) = ... V(i-1)+ V (i 3) for i≥ 3 It can be shown that the recurrence for V(i) in part (i) satisfies V(i) = (a¹), for a constant a > 1. (You can prove this by establishing by induction on i that V(i) ≥ cai-³ for a suitable constant c, but you do not need to submit this derivation.) Activate (ii) (2 pts) Establish with a proof whether or not the maximum degree of any node in anyett n-element 3F heap is O(logn). Consider the DECREASE-KEY operation in a Fibonacci heap. Let us generalize the cascading-cut rule to cut a node x from its parent as soon as it loses its third child (this extends the method in the lecture which cut x from its parent if it loses its second child). Let us call this a 3F heap. Assume the following fact for the 3F heap (you can prove this on your own, you do not need to submit your proof). 7 Fact. Let a be a node in a 3F heap, and let its degree be d. Let y₁, yd be the children of r in the order in which they were linked to x, from the earliest to the latest. Establish that the degree of yi is at least i - 3 for i ≥ 3. (i) (6 pts) Let x be a node of degree d in a 3F heap and let size(r) be the number of nodes in the subtree rooted at r. Establish that size(x) ≥ V(d), where V(i) satisfies the following: V(i) =i+1 for 0 ≤ i ≤ 2, and V(i) = ... V(i-1)+ V (i 3) for i≥ 3 It can be shown that the recurrence for V(i) in part (i) satisfies V(i) = (a¹), for a constant a > 1. (You can prove this by establishing by induction on i that V(i) ≥ cai-³ for a suitable constant c, but you do not need to submit this derivation.) Activate (ii) (2 pts) Establish with a proof whether or not the maximum degree of any node in anyett n-element 3F heap is O(logn).

Answer rating: 100% (QA)

i We will prove this by induction on d Base Case d 0 1 2 For d 0 x has no children so the claim is vacuously true For d 1 x has one child y1 By the fa... View the full answer