Computer Science CSC263H St. George Campus
February 1, 2018 University of Toronto
Solutions for Homework Assignment #2
Answer to Question 1.
a. A binomial heap H with n vertices consists of α(n) trees. Let Ti, 1 ≤ i ≤ α(n), denote the trees of
H. A tree Ti with ni vertices has ni − 1 edges. So the total number of edges in H is i=α(n)(ni − 1) =
(i=α(n) ni) − α(n) = n − α(n) i=1
b. Binomial heap H has n nodes before the insertions. Thus, by Part (a), H has n − α(n) edges before the insertions. After the k consecutive insertions, H has n + k nodes, hence it now has (n + k) − α(n + k) edges. So the number of new edges created by the k consecutive insertions is:
[(n + k) − α(n + k)] − [n − α(n)] = k + α(n) − α(n + k) ≤ k + α(n) edges.
As we explained in class, the number of pairwise comparisons between the keys of H needed to execute k consecutive insertions is equal to the number of new edges created by these insertions: each key comparison creates a new edge in H and each new edge in H comes from a key comparison. So k consecutive insertions require at most k + α(n) key comparisons.
By definition α(n) is the number of 1’s in the binary representation of n, therefore, α(n) ≤ ⌊log2 n⌋+1. So k consecutive insertions require at most k + ⌊log2 n⌋ + 1 comparisons, and the average cost per insertion is at most (k+⌊log2 n⌋+1)/k = 1+⌊log2 n⌋/k+1/k. Thus, for k > logn, this average cost is less than 3.
Answer to Question 2. We define a procedure Check which takes a pointer u to a tree node and returns the following:
• (nil, nil) if the tree rooted at u is not 2-balanced;
• a pair of numbers (r, h), where r = radius(u) and h = height(u), if the tree rooted at u is 2-balanced.
The procedure follows: Check(u)
1 2 3 4 5 6 7 8 9
10
11
12
13
14
15
16
17
18
19
20
21
ifu==nil
return (−1, −1)
elseif u.lchild == nil
(rR,hR) = Check(u.rchild) if rR ==nil
return (nil, nil)
else return (rR + 1, hR + 1)
elseif u.rchild == nil
(rL , hL ) = Check(u. lchild ) ifrL==nil
else
return (nil, nil) elsereturn(rL+1,hL+1) (rL , hL ) = Check(u. lchild ) (rR , hR ) = Check(u. rchild ) if rL ==nil or rR ==nil
return (nil, nil) r=min(rL,rR)+1 h=max(hL,hR)+1 ifh≤2r
return (r, h) else return (nil, nil)
To check that T is 2-balanced, we call Check with a pointer to the root of T. The procedure takes Θ(n) time since it visits each vertex of T exactly once.
1
i=1