20.4 Bounding the maximum degree

| < Day Day Up > |

## 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 y1, y2, . . . , yk denote the children of x in the order in which they were linked to x, from the earliest to the latest. Then, degree[y1] ≥ 0 and degree[yi] ≥ i - 2 for i = 2, 3, . . . , k.

Proof Obviously, degree[y1] ≥ 0.

For i ≥ 2, we note that when yi was linked to x, all of y1, y2, . . . , yi-1 were children of x, so we must have had degree[x] = i - 1. Node yi is linked to x only if degree[x] = degree[yi], so we must have also had degree[yi] = i - 1 at that time. Since then, node yi has lost at most one child, since it would have been cut from x if it had lost two children. We conclude that degree[yi ] ≥ 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 Fk.

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)

Fk+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) ≥ Fk+2 ≥ φk, where .

Proof Let sk denote the minimum possible value of size(z) over all nodes z such that degree[z] = k. Trivially, s0 = 1, s1 = 2, and s2 = 3. The number sk is at most size(x), and clearly, the value of sk increases monotonically with k. As in Lemma 20.1, let y1, y2, . . . , yk 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 y1 (for which size(y1) ≥ 1), giving

where the last line follows from Lemma 20.1 (so that degree[yi] ≥ i - 2) and the monotonicity of sk (so that sdegree [yi] ≥ si-2).

We now show by induction on k that sk ≥ Fk+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 si ≥ Fi+2 for i = 0, 1, . . . , k - 1. We have

Thus, we have shown that size(x) ≥ sk ≥ Fk+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.)

| < Day Day Up > |