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.
2Theprobabilityhastobeintheformata∗10n whereaisarealnumbersuchthat1≤a<10andnisaninteger 5