Question 5 [10 marks]
The max-heap operations we covered in class only allow for inserting a new element, finding the largest element, or extracting that largest element. In this question, you will develop two new operations: changing the priority of an element and removing a non-root element:
1. Given H, an array representing a max-heap, and x, a pointer to an element in H, give a pseudocode implementation for ChangePriority(H, x, new priority). This operation changes x.priority to new priority. Postcondition: H is max-heap. Your algorithm must run in ¦¨(log n) worst-case time, where n is the number of elements contained in the heap. You do not need to justify the worst-case running time of your algorithm, but must implement it in the most efficient way possible (space and runtime wise). Do not use any operations implemented in class. You can access the index of x in H with x.i if you need it.
2. In Q7 from Week 3 worksheet, you saw a specific scenario for analysing the average number of calls to TREE-SEARCH. In this question, construct a specific scenario and necessary assumptions to analyse the average number of swaps ChangePriority is expected to perform on that scenario you come up with. HINT: define a specific max-heap with 9-15 elements, choose an element to perform the analysis on, and then do the calculations on a range of new priorities chosen uniformly and randomly from a set.
3. Given H, an array representing a max-heap, and x, a pointer to an element in H, write the pseudocode for an efficient algorithm which only uses Insert(H, x), ExtractMax(H), and ChangePriority(H, x, new priority) to implement the new operation RemoveItem(H, x) in logarithmic time. This new operation deletes an element without returning its value. Postcondition: H is max-heap. You may assume that you are given a correct implementation of ChangePriority(H, x, new priority).
4. In 2-3 sentences, make an argument for the correctness of your RemoveItem(H,x) implementation and that it runs in logarithmic time.
6