Introduction To Algorithms 2Nd Edition Incl Exercises Edition [Electronic resources] نسخه متنی

20.4 Bounding the maximum degree

To prove that the amortized time of FIB-HEAP-EXTRACT-MIN and FIB-HEAP-DELETE is O(lg n), we must show that the upper bound D(n) on the degree of any node of an n-node Fibonacci heap is O(lg n). By Exercise 20.2-3, when all trees in the Fibonacci heap are unordered binomial trees, D(n) = ⌊lg n⌋. The cuts that occur in FIB-HEAP-DECREASE-KEY, however, may cause trees within the Fibonacci heap to violate the unordered binomial tree properties. In this section, we shall show that because we cut a node from its parent as soon as it loses two children, D(n) is O(lg n). In particular, we shall show that D(n) ≤ ⌊log_φn⌋, where .

The key to the analysis is as follows. For each node x within a Fibonacci heap, define size(x) to be the number of nodes, including x itself, in the subtree rooted at x. (Note that x need not be in the root list-it can be any node at all.) We shall show that size(x) is exponential in degree[x]. Bear in mind that degree[x] is always maintained as an accurate count of the degree of x.

Lemma 20.1

Let x be any node in a Fibonacci heap, and suppose that degree[x] = k. Let y₁, y₂, . . . , y_k denote the children of x in the order in which they were linked to x, from the earliest to the latest. Then, degree[y₁] ≥ 0 and degree[y_i] ≥ i - 2 for i = 2, 3, . . . , k.

Proof Obviously, degree[y₁] ≥ 0.

For i ≥ 2, we note that when y_i was linked to x, all of y₁, y₂, . . . , y_i-1 were children of x, so we must have had degree[x] = i - 1. Node y_i is linked to x only if degree[x] = degree[y_i], so we must have also had degree[y_i] = i - 1 at that time. Since then, node y_i has lost at most one child, since it would have been cut from x if it had lost two children. We conclude that degree[y_i ] ≥ i - 2.

We finally come to the part of the analysis that explains the name "Fibonacci heaps." Recall from Section 3.2 that for k = 0, 1, 2, . . . , the kth Fibonacci number is defined by the recurrence

The following lemma gives another way to express F_k.

Lemma 20.2

For all integers k ≥ 0,

Proof The proof is by induction on k. When k = 0,

We now assume the inductive hypothesis that , and we have

The following lemma and its corollary complete the analysis. They use the in-equality (proved in Exercise 3.2-7)

F_k+2 ≥ φ^k,

where φ is the golden ratio, defined in equation (3.22) as .

Lemma 20.3

Let x be any node in a Fibonacci heap, and let k = degree[x]. Then, size(x) ≥ F_k+2 ≥ φ^k, where .

Proof Let s_k denote the minimum possible value of size(z) over all nodes z such that degree[z] = k. Trivially, s₀ = 1, s₁ = 2, and s₂ = 3. The number s_k is at most size(x), and clearly, the value of s_k increases monotonically with k. As in Lemma 20.1, let y₁, y₂, . . . , y_k denote the children of x in the order in which they were linked to x. To compute a lower bound on size(x), we count one for x itself and one for the first child y₁ (for which size(y₁) ≥ 1), giving

where the last line follows from Lemma 20.1 (so that degree[y_i] ≥ i - 2) and the monotonicity of s_k (so that s_{degree [yi]} ≥ s_i-2).

We now show by induction on k that s_k ≥ F_k+2 for all nonnegative integer k. The bases, for k = 0 and k = 1, are trivial. For the inductive step, we assume that k ≥ 2 and that s_i ≥ F_i+2 for i = 0, 1, . . . , k - 1. We have

Thus, we have shown that size(x) ≥ s_k ≥ F_k+2 ≥ φ^k.

Corollary 20.4

The maximum degree D(n) of any node in an n-node Fibonacci heap is O(lg n).

Proof Let x be any node in an n-node Fibonacci heap, and let k = degree[x]. By Lemma 20.3, we have n ≥ size(x) ≥ φ^k. Taking base-φ logarithms gives us k ≤ log_φ n. (In fact, because k is an integer, k ≤ ⌊log_φ n⌋.) The maximum degree D(n) of any node is thus O(lg n).

Exercises 20.4-1

Professor Pinocchio claims that the height of an n-node Fibonacci heap is O(lg n). Show that the professor is mistaken by exhibiting, for any positive integer n, a sequence of Fibonacci-heap operations that creates a Fibonacci heap consisting of just one tree that is a linear chain of n nodes.

Exercises 20.4-2

Suppose we generalize the cascading-cut rule to cut a node x from its parent as soon as it loses its kth child, for some integer constant k. (The rule in Section 20.3 uses k = 2.) For what values of k is D(n) = O(lg n)?

Problems 20-1: Alternative implementation of deletion

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

PISANO-DELETE(H, x)
1  if x = min[H]
2     then FIB-HEAP-EXTRACT-MIN(H)
3     else y ← p[x]
4          if y ≠ NIL
5             then CUT(H, x, y)
6                  CASCADING-CUT(H, y)
7          add x's child list to the root list of H
8          remove x from the root list of H

1. 
   

   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?



2. 
   

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



3. 
   

   Suppose that we call 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 degree[x], c, t(H), and m(H).

   
   



4. 
   

   Conclude that the amortized time for PISANO-DELETE is asymptotically no better than for FIB-HEAP-DELETE, even when x ≠ min[H].

Problems 20-2: More Fibonacci-heap operations

We wish to augment a Fibonacci heap H to support two new operations without changing the amortized running time of any other Fibonacci-heap operations.

1. 
   

   The operation FIB-HEAP-CHANGE-KEY(H, x, k) changes the key of node x to the value k. Give an efficient implementation of FIB-HEAP-CHANGE-KEY, and analyze the amortized running time of your implementation for the cases in which k is greater than, less than, or equal to key[x].



2. 
   

   Give an efficient implementation of FIB-HEAP-PRUNE(H, r), which deletes min(r, n[H]) nodes from H. Which nodes are deleted should be arbitrary. Analyze the amortized running time of your implementation. (Hint: You may need to modify the data structure and potential function.)