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.

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

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.

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).

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.

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)?

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].

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.)