1. [15pts] In many practical applications such as Prims algorithm for computing a minimum spanning tree and Dijkstras algorithm for computing shortest paths, both of which we will see later in this course, the priority queue ADT needs to be expanded to include the operation of changing the priority of an element. Design and give pseudocode as well as analyze the algorithm ChangePriority(Q,x,v), which changes the priority value of an element x in the priority queue Q to v when Q is implemented as a min-heap. ChangePriority should have worst-case complexity O(log n), where n is the number of elements in the min-heap.

Hint. Consider two cases, the priority is decreased and the priority is increased and correct a min-heap property violation in a similar way to what we did for insertion and deletion into a min-heap.