In this homework, you should augment the HeapPriorityQueue class from here by providing an implementation of the replaceValue, replaceKey, and remove methods, which are currently just stubs. Note that the HeapPriorityQueue class is the one we developed in the lectures for implementing a priority queue using a heap. The addition of these three methods will turn it into an adaptable priority queue.

The implementations of the new methods should run in O(log n) time, where n is the number of entries in the priority queue. As discussed in the lecture on Friday, Dec 6, the main new idea needed to achieve this running time is to make each MyEntry object location aware: each such object will have an additional field that remembers the index in the ArrayList heap that contains the object. Feel free to modify the MyEntry class as needed, and also feel free to define other types of Exception classes that you may need.

Chapter 8 is a general reference for priority queues, heaps, and adaptable priority queues, but the specific task for this homework is not discussed there.

Submit the source files into a dropbox in ICON called Homework9. This assignment is due by 11:59 pm on Wednesday, Dec 11.

Note (added Dec 9): To make MyEntry location aware, you will also need to make other changes in HeapPriorityQueue: for example, when the insert method adds a new MyEntry object to the heap, the index field should be set correctly; the swap method also needs to set indices correctly.