CSC263H1, Fall 2019 Problem Set 2 Sample Solutions
CSC263H1: Problem Set 2 Sample Solutions
Due Tuesday September 24 before 10pm
Note: solutions may be incomplete, and meant to be used as guidelines only. We encourage you to ask follow-up questions on the course forum or during office hours.
1. [10 marks] Heaps. Consider a max-priority queue Q implemented using a binary max-heap. We would like to design an ExtractSecondLargest(Q) operation, which returns the second largest key in Q and deletes it from Q. The worst-case running time of this operation must be in O(log n). We assume that all keys in Q are distinct integers.
(a) [6 marks] Write the pseudo-code of your ExtractSecondLargest(Q) algorithm. Let Q be an array whose indices start from 1. You can use operations from the textbook and lectures as helpers without describing their details.
Solution
ExtractSecondLargest(Q) : if Q.heapsize ≤ 1 :
error “Second largest does not exist!” index2nd ← 2
if Q.heapsize ≥ 3 and Q[3] > Q[2] : index2nd ← 3
result ← Q[index2nd] IncreaseKey(Q, index2nd, +∞) ExtractMax(Q)
return result
Other implementations that also work:
1. Swap Q[index2nd] (the larger of Q[2] and Q[3]) with Q[Q.heapsize] (the last one), decrement Q.heapsize, then call BubbleDown/Heapify(Q, index2nd).
2. Call ExtractMax twice, and Insert back the max returned by the first ExtractMax.
(b) [2 marks] Explain why your pseudo-code works correctly. In particular, explain why the element you extract is the second largest one, and why this operation maintains the heap property.
Solution
According to the max-heap property, the second largest key in Q must be the larger one between the two children of the root, i.e., the larger one between Q[2] and Q[3], which is the result returned by the pseudo-code.
IncreaseKey(Q, index2nd, +∞) bubbles-up the second largest key to the root position (with max key). Then ExtractMax(Q) deletes it from Q, which is exactly the desired behaviour.
(c) [2 marks] Explain why the worst-case running time of your algorithm is in O(log n).
Solution
The running time of ExtractSecondLargest is constant time plus the running time of
Page 1/5
CSC263H1, Fall 2019 Problem Set 2 Sample Solutions
IncreaseKey and ExtractMax, which are both O(logn) in worst-case. So the worst-case running time of this implementation of ExtractSecondLargest is in O(log n).
Page 2/5
CSC263H1, Fall 2019 Problem Set 2 Sample Solutions
2. [20 marks] Expected cost. Consider a min-priority queue Q implemented using a binary min-heap. Let k ∈ N be a given natural number. Suppose that Q contains n = 2k − 1 elements (or “nodes”), with indices 1 . . . n. Let aj be the value stored in the element with index 2j−1.
Let x ∈ Z be a given integer. Let m be a random variable corresponding to the number of swaps performed by Q.insert(x).
Letpbeagivenrealnumber,0