Question 4 [10 marks]
Suppose that you have a set of all the unique and even integers from 6 to 60 inclusive. Build a max-
heap from these values such that if you were to insert 33 into the completed max-heap, restoring the
heap property would bubble the 33 all the way up to one of the root’s immediate children. Then
answer the following questions:
1. Draw the initial max heap (before 33 is inserted) and the final heap (after 33 is inserted and
bubbled up).
2. Instead of building the heap from the previous part manually, you decide to use a random list
generator (we’re on a roll with randomized algorithms in this problem set!). Specifically, you
use the generator to populate an array with the unique even integers from 6 to 60 (so no 33).
What is the probability that the resulting array represents a valid max-heap? Explain your
work, show your calculations, and write the final answer using scientific (exponential) notation2.
The following resource might be helpful for probability calculation [http://oeis.org/A056971].
Based on the resulting probability, is this a good way to build a heap compared to the other two
techniques we saw in class?
3. Go back to your initial heap from part 1 (so before inserting 33), and make a copy of it with only
the first 8 elements (so elements with array index 1 through 8). Run Heapsort on this 8-element
heap to generate a sorted array. Show all the intermediate arrays like we did in Week 2 lecture.
4. Is Heapsort Order-Respecting? We define an Order-Respecting sorting algorithm as that where
elements with identical priorities in the input array remain in the same order relative to each
other in the output array. For example, if the input array (or heap) was [5, *4, +4, 2] (the * and
+ distinguish between the elements with identical priorities), and the outcome of Heapsort is [2,
+4, *4, 5], then this sorting algorithm is not Order-Respecting. If Heapsort is Order-Respecting,
provide a proof. If not, insert some elements with duplicate priorities into the unsorted 8-element
heap from the previous part and walk us through a counterexample.
2The probability has to be in the format a ∗ 10n where a is a real number such that 1 ≤ a < 10 and n is an integer 5